function quickSort(arr) {
// 長度小於 1 直接返回,作為遞迴終止條件
if (arr.length < 1) {
return arr;
}
// 取中間那個數作為基準點,索引若非整數則向下取整
var centerIndex = Math.floor(arr.length / 2);
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]);
}
}
return quickSort(arrLeft).concat(centerNum, quickSort(arrRight));
}
var arrSort = [33, 18, 2, 40, 16, 63, 27];
console.log(quickSort(arrSort));
快速排序的三個動作:
找基準點——取陣列中間的一個數。
分區——以基準點為界,把剩下的數分成兩個新陣列,小的放左邊,大的放右邊。
遞迴——在函數內部呼叫自身,對左右兩個子陣列重複上述過程。
第一次執行:中間數是 40。迴圈中比 40 小的進 arrLeft,比 40 大的進 arrRight。

第二次呼叫:執行到 return quickSort(arrLeft).concat(centerNum, quickSort(arrRight)) 時,quickSort(arrLeft) 傳入的參數是 [33,18,2,16,27]。中間數是 2,比 2 小的放左邊,比 2 大的放右邊。

後面一樣是循環呼叫自己,直到傳入的參數長度小於 1,就把該參數返回,遞迴開始回捲並逐層拼接。
等於基準點的元素被丟掉了。上面用 < 和 > 兩個判斷,值等於 centerNum 的元素既不進 arrLeft 也不進 arrRight。示例陣列沒有重複值所以看不出問題,但 [5, 5, 5] 這樣的輸入會直接丟失資料。修正方式是把 >= 歸到某一側,或者改用三路分割(小於/等於/大於)。
splice 會修改原陣列。示例裡 arr.splice(centerIndex, 1) 直接把基準點從原陣列移除了,如果不想動到傳入的陣列,應該改用切片:var mid = arr[centerIndex],然後在迴圈裡跳過該索引。
concat 需要注意型別。centerNum 是 splice 返回的陣列(如 [40]),所以 concat(centerNum, ...) 正好能正確展開。如果改成存 arr[centerIndex] 得到的是數字,就要寫成 concat([centerNum], ...),否則 concat 仍會把它當單個元素追加,結果倒是相同,但語義容易誤解。
效能。這個實現每次都建立新陣列,額外的記憶體配置與拷貝開銷不小,平均時間複雜度是 O(n log n),但空間複雜度退化為 O(n)。生產環境的首選是原地分割(in-place)版本,空間可降到 O(log n)。