這段程式碼來自「妙味課堂」的一期教學影片,我自己重寫並補上註解後記錄下來。
function quickSort(arr) {
// 長度不足 1 就直接返回,這是遞迴的出口
if (arr.length < 1) {
return arr;
}
// 取中間索引,浮點數要向下取整
var centerIndex = Math.floor(arr.length / 2);
// 用 splice 把基準點取出來
var centerNum = arr.splice(centerIndex, 1);
var arrLeft = []; // 比基準點小的放左邊
var arrRight = []; // 比基準點大的放右邊
for (var i = 0; i < arr.length; i++) {
if (arr[i] < centerNum) {
arrLeft.push(arr[i]);
} else if (arr[i] > centerNum) {
arrRight.push(arr[i]);
}
}
// 左右各自再排一次,然後用 concat 拼回來
return quickSort(arrLeft).concat(centerNum, quickSort(arrRight));
}
var arrSort = [33, 18, 2, 40, 16, 63, 27];
console.log(quickSort(arrSort));基準點:取陣列中間位置的那個數。
雙陣列分裝:以基準點為界,小的丟進左陣列,大的丟進右陣列。
遞迴:函數內部呼叫自己,直到子陣列長度小於 1 才停止。
1. 一定要有一個會 return 的中止條件,否則就是死迴圈。
2. 內部呼叫自己時傳入的參數,要與首次傳入的參數存在關聯(這裡是「比基準點小/大的子集合」)。
3. 需要重複執行同一套動作的問題,就可以考慮用遞迴。
第一次呼叫,中間數是 40。迴圈判斷後,小於 40 的進 arrLeft,大於 40 的進 arrRight:

接著執行到 return quickSort(arrLeft).concat(centerNum, quickSort(arrRight)),quickSort(arrLeft) 收到的參數是 [33, 18, 2, 16, 27],這次的中間數是 2,比 2 小的放左邊,比 2 大的放右邊:

之後再呼叫 quickSort(arrRight),一路遞迴下去,直到傳入的陣列長度小於 1,就把該陣列原樣返回,這一層的排序才算完成。
這裡有個實作細節值得留意:centerNum 是陣列,因此比較時會發生型別轉換,雖然在數字範例中結果正確,若要更嚴謹可改成先取出純值再比較。