快速排序是理解「分治法」最好的入門案例:選一個基準值,把陣列分成「比它小」和「比它大」兩堆,再各自遞迴排序,合併起來就是答案。用 JavaScript 寫出來可以非常短,因為陣列的 splice 與 concat 幫我省掉了大量底層操作。
<html>
<head>
<script>
function quickSort(input) {
// 長度 0 或 1 代表已排序完成,這是遞迴的終止條件
if (input.length <= 1) return input;
// 隨機挑一個基準值,避免已排序資料退化為 O(n²)
var pivot = Math.floor(Math.random() * input.length);
var less = [], greater = [];
var pivotElem = input.splice(pivot, 1); // 取出並移除基準值
for (var x in input) {
if (input[x] <= pivotElem[0]) less.push(input[x]);
else greater.push(input[x]);
}
// 合併:左半 + 基準 + 右半
return [].concat(quickSort(less), pivotElem, quickSort(greater));
}
// 產生測試資料:1000 筆 0~99 的隨機整數
var input = [];
var inputSize = 1000;
var highestInputValue = 100;
for (var i = 0; i < inputSize; i++) {
input.push(Math.floor(Math.random() * highestInputValue));
}
document.writeln(quickSort(input));
</script>
</head>
<body></body>
</html>
1. 終止條件。長度 ≤ 1 直接回傳,這是遞迴一定要有的出口。
2. 隨機選基準。若固定取第一個元素,遇到已排序或接近排序的資料時會退化成 O(n²)。隨機挑選能有效降低機率,實務上更常見的是「三取中」——從頭、中、尾取中位數。
3. splice 取出基準。把基準從原陣列移出,迴圈就只需處理剩下的元素。
4. concat 合併。依序拼接「排好的左半、基準、排好的右半」,一步完成組裝。
1. 可讀性優先,不是效能優先。它每次都配置新陣列(less、greater、concat 的結果),空間複雜度是 O(n),而原地版的 quicksort 只需 O(log n) 的堆疊空間。
2. for...in 不適合遍歷陣列。它走的是可列舉屬性名稱而非索引,順序不保證,也可能撈到原型鏈上被擴充的屬性。改成 for (var i = 0; i < input.length; i++) 才是正確做法。
3. document.writeln 有風險。頁面載入完成後呼叫它會清空整個文件,除教學外請改用 console.log 或寫入特定元素。
4. 相等元素會全部塞進 less。大量重複值時左右子陣列大小會失衡。若要處理這種資料,可改成三路分割(小於/等於/大於)。
實務上直接呼叫 input.sort((a, b) => a - b) 就好。V8 對數字陣列的排序已有高度優化,通常快過手寫版本;自己實作的價值主要在於理解演算法與應付面試。