快速排序平均時間複雜度 O(n log n),但最壞情況(已排序/接近有序數組)退化為 O(n²)。隨機化選取主元可將最壞情況概率降至極低,保證期望時間複雜度 O(n log n)。
/**
* 隨機化快速排序
* @param {Array} arr - 待排序數組(原地修改)
* @param {Number} low - 起始索引
* @param {Number} high - 結束索引
* @returns {Array} 排序後的數組
*/
function randomizedQuickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
// 隨機選取主元並與 low 位置交換
const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
[arr[low], arr[randomIdx]] = [arr[randomIdx], arr[low]];
// 分區
const pivotIdx = partition(arr, low, high);
// 遞歸排序左右子數組
randomizedQuickSort(arr, low, pivotIdx - 1);
randomizedQuickSort(arr, pivotIdx + 1, high);
}
return arr;
}
/**
* 分區函數:以 arr[low] 為基準,小於基準的移左側,大於的移右側
* @returns {Number} 基準元素最終位置索引
*/
function partition(arr, low, high) {
const pivot = arr[low];
let i = low;
for (let j = low + 1; j <= high; j++) {
if (arr[j] <= pivot) {
i++;
if (i !== j) [arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[low], arr[i]] = [arr[i], arr[low]];
return i;
}
// 測試
const testCases = [
[33, 22, 11, 88, 23, 32],
[1, 2, 3, 4, 5], // 已排序
[5, 4, 3, 2, 1], // 逆序
[3, 3, 3, 3], // 全相同
[], // 空數組
[42] // 單元素
];
testCases.forEach(arr => {
const copy = [...arr];
console.log('原始:', copy.join(','));
console.log('排序:', randomizedQuickSort(copy).join(','));
console.log('---');
});
const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
// 等價於:Math.floor(Math.random() * (high - low + 1)) + low
在 [low, high] 區間均勻隨機選取索引,打破有序數組的最壞情況。
空間複雜度 O(log n)(遞歸棧),無需額外數組空間。
function partition3Way(arr, low, high) {
const pivot = arr[low];
let lt = low, gt = high, i = low + 1;
while (i <= gt) {
if (arr[i] < pivot) [arr[lt++], arr[i++]] = [arr[i], arr[lt]];
else if (arr[i] > pivot) [arr[i], arr[gt--]] = [arr[gt], arr[i]];
else i++;
}
return [lt, gt]; // 返回等於區間邊界
}
| 指標 | 複雜度 | 說明 |
|---|---|---|
| 平均時間 | O(n log n) | 隨機化保證期望性能 |
| 最壞時間 | O(n²) | 極小概率(主元連續極值) |
| 空間 | O(log n) | 遞歸棧深度 |
| 穩定性 | 不穩定 | 相等元素相對位置可能改變 |
實際項目中優先使用原生 Array.prototype.sort()(V8 引擎採用 Timsort 混合算法),僅在教學、特殊性能需求或面試時手寫快排。