快速排序平均時間複雜度 O(n log n),但面對已排序或近乎排序陣列會退化至 O(n²)。隨機化快速排序透過隨機選取主元,確保期望時間複雜度穩定於 O(n log n)。本文提供完整的 JS 實作與測試代碼。
array[low] 為基準,將小於等於基準的元素移至左側,返回最終基準位置 w。[low, high] 區間隨機選取索引 v,交換 array[low] 與 array[v],再呼叫 split 並遞迴處理左右子陣列。/**
* 分區函數
* @param {Array} array 待排序陣列
* @param {number} low 起始索引
* @param {number} high 結束索引
* @returns {number} 基準元素最終位置
*/
function split(array, low, high) {
let i = low;
const x = array[low];
for (let j = low + 1; j <= high; j++) {
if (array[j] <= x) {
i++;
if (i !== j) {
[array[i], array[j]] = [array[j], array[i]]; // ES6 解構交換
}
}
}
[array[low], array[i]] = [array[i], array[low]];
return i;
}
/**
* 隨機化快速排序
* @param {Array} array 待排序陣列
* @param {number} low 起始索引
* @param {number} high 結束索引
* @returns {Array} 排序後陣列(原地排序並返回)
*/
function rquicksort(array, low, high) {
if (low < high) {
// 隨機選取主元
const v = Math.floor(Math.random() * (high - low + 1)) + low;
[array[low], array[v]] = [array[v], array[low]];
const w = split(array, low, high);
rquicksort(array, low, w - 1);
rquicksort(array, w + 1, high);
}
return array;
}
// 測試
const arr = [33, 22, 11, 88, 23, 32];
console.log("排序前:", arr);
console.log("排序後:", rquicksort(arr, 0, arr.length - 1));
Math.floor(Math.random() * (high - low + 1)) + low 產生 [low, high] 區間內的隨機整數。[a, b] = [b, a] 簡化交換邏輯,舊環境可改用暫存變數。| 情況 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| 平均 | O(n log n) | O(log n) 遞迴堆疊 |
| 最壞(極罕見) | O(n²) | O(n) |
// 使用 Jest / Mocha 等測試框架
test("randomized quicksort", () => {
const data = [5, 2, 9, 1, 5, 6];
expect(rquicksort([...data], 0, data.length - 1)).toEqual([1, 2, 5, 5, 6, 9]);
});