快速排序的思想相當好懂,整個過程只要三個步驟:
<script type="text/javascript">
function quickSort(arr) {
if (arr.length <= 1) {
return arr; // 如果陣列只有一個數,就直接返回
}
var num = Math.floor(arr.length / 2); // 找到中間數的索引值,如果是浮點數則無條件捨去
var numValue = arr.splice(num, 1); // 取出中間數作為基準點
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < numValue) {
left.push(arr[i]); // 比基準點小的丟左邊
} else {
right.push(arr[i]); // 其餘的丟右邊
}
}
// 遞迴不斷重複比較
return quickSort(left).concat([numValue], quickSort(right));
}
alert(quickSort([32, 45, 37, 16, 2, 87])); // 彈出 "2,16,32,37,45,87"
</script>
以 [32, 45, 37, 16, 2, 87] 為例:中間索引是 3,取出 16 當基準點,剩下的元素分成 [2] 與 [45, 37, 87] 兩堆。左邊只有一個元素,直接回傳;右邊再取一次中間值繼續切分。最後用 concat 把「左邊 + 基準點 + 右邊」拼回去,就得到有序結果。
第一,arr.splice(num, 1) 會回傳一個陣列,所以程式裡用 [numValue] 把它包成陣列再拼接——這樣做剛好讓基準點以陣列形式參與 concat,寫得有點巧妙但也容易讓人誤解,改成 var numValue = arr.splice(num, 1)[0]; 再寫 concat([numValue], ...) 語意會清楚得多。
第二,這個版本平均時間複雜度是 O(n log n),但它每次都建立新陣列,空間成本偏高,複製操作也不便宜。若想更進一步,可以在原陣列上以雙指標做原地分區(in-place partition),把額外空間降到 O(log n)。
快速排序在資料量不大時通常比合併排序快,但最壞情況(每次基準點都取到極值)會退化為 O(n²),隨機選基準點或三數取中都能有效降低這個風險。