萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 實現隨機化快速排序算法

算法背景

快速排序平均時間複雜度 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('---');
});

關鍵點解析

1. 隨機化主元選取


const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
// 等價於:Math.floor(Math.random() * (high - low + 1)) + low

在 [low, high] 區間均勻隨機選取索引,打破有序數組的最壞情況。

2. 原地分區

空間複雜度 O(log n)(遞歸棧),無需額外數組空間。

3. 三向切分優化(處理大量重複元素)


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)遞歸棧深度
穩定性不穩定相等元素相對位置可能改變

現代 JS 排序實踐

實際項目中優先使用原生 Array.prototype.sort()(V8 引擎採用 Timsort 混合算法),僅在教學、特殊性能需求或面試時手寫快排。

copyright © 萬盛學電腦網 all rights reserved