DIV CSS 佈局教程網

快速排序在 PHP 與 JavaScript 中的實作差異
編輯:關於JavaScript     

同一套分治邏輯,換成不同語言就得注意語病。以下用 PHP 與 JavaScript 各寫一遍快速排序,順便點出關鍵差異。

1. PHP 版本

<?php
$unsorted = array(2, 4, 5, 63, 4, 5, 63, 2, 4, 43);

function quicksort($array)
{
    if (count($array) == 0)
        return array();
    $pivot = $array[0];
    $left = $right = array();
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $pivot)
            $left[] = $array[$i];
        else
            $right[] = $array[$i];
    }
    return array_merge(quicksort($left), array($pivot), quicksort($right));
}

$sorted = quicksort($unsorted);
print_r($sorted);

2. JavaScript 版本

var a = [2, 4, 5, 63, 4, 5, 63, 2, 4, 43];

function quicksort(arr) {
    if (arr.length == 0)
        return [];
    var left = new Array();
    var right = new Array();
    var pivot = arr[0];
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort(a));

3. 終止條件的差別

兩個版本的第一個條件判斷都至關重要,但為什麼寫法不同?

在 PHP 中,count 函式對空陣列會回傳 0,因此可以寫得更寬鬆:

if (count($array) < 2)
    return $array;

元素少於 2 個的陣列必然已排序,直接回傳即可,這比判斷等於 0 更有效率——少一層遞迴呼叫。

但在 JavaScript 中這個寫法會出問題。當傳入 undefined 作為參數時,arr.length 會拋出錯誤,而空陣列與 undefined 的行為並不相同:

// 這樣寫會出錯
if (arr.length < 2)
    return arr;

因此 JavaScript 版本必須明確判斷 arr.length == 0,把遞迴的正確終止條件講清楚。這正是同一份演算法跨語言移植時最容易忽略的地方:語法看似對應,語意卻未必等價。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved