萬盛學電腦網

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

JavaScript 實現隨機化快速排序演算法完整代碼

前言

快速排序平均時間複雜度 O(n log n),但面對已排序或近乎排序陣列會退化至 O(n²)。隨機化快速排序透過隨機選取主元,確保期望時間複雜度穩定於 O(n log n)。本文提供完整的 JS 實作與測試代碼。

演算法核心

  1. split(分區):以 array[low] 為基準,將小於等於基準的元素移至左側,返回最終基準位置 w。
  2. rquicksort(遞迴):在 [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] 區間內的隨機整數。
  • 使用 ES6 解構賦值 [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]);
});
copyright © 萬盛學電腦網 all rights reserved