同一套分治邏輯,換成不同語言就得注意語病。以下用 PHP 與 JavaScript 各寫一遍快速排序,順便點出關鍵差異。
<?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);
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));
兩個版本的第一個條件判斷都至關重要,但為什麼寫法不同?
在 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,把遞迴的正確終止條件講清楚。這正是同一份演算法跨語言移植時最容易忽略的地方:語法看似對應,語意卻未必等價。