← 返回首頁

🔺 雙調排序法

Bitonic Sort - 演算法概念與互動示範

什麼是雙調排序法？

雙調排序法是一種使用「雙調序列」的排序演算法，先將資料分割成遞增與遞減兩段，再透過合併步驟將它們轉成完整排序序列。

雙調序列

雙調序列由一段遞增和一段遞減序列組成，像是一個菱形或山形，稱為 bitonic sequence。

演算法步驟

  1. 把陣列分成兩個子序列，一個升冪、一個降冪。
  2. 對兩個子序列遞迴進行雙調排序。
  3. 執行雙調合併，將雙調序列整理成完全排序結果。

特性

  • 平行友善：非常適合硬體加速或 SIMD 平行運算。
  • 穩定性：演算法本身非穩定排序。
  • 空間：主要使用遞迴和少量額外空間。
  • 適合規格：在需要可預測比較步驟的情境中表現良好。

互動演示

比較次數：0

交換次數：0

當前步驟：就緒

時間與空間複雜度

情景 時間複雜度 說明
最好情況 O(n log² n) 比較次數固定，與輸入順序無關
平均情況 O(n log² n) 遞迴合併需要多層比較
最壞情況 O(n log² n) 固定深度的比較模式
空間複雜度 O(log² n) 遞迴消耗額外堆疊空間

示範步驟

若要理解雙調排序法，可以想像先把序列切成兩段，讓一段升冪、一段降冪，然後透過多次比較與交換，讓整個序列有序。

  1. 建立雙調序列(bitonic sequence)。
  2. 執行 bitonic merge。
  3. 遞迴處理左右子序列，直到每段長度為 1。
  4. 最終回傳完整排序陣列。

虛擬碼與實際程式碼對照

下方比較展示了雙調排序法的關鍵步驟與對應的 JavaScript 實作，讓演算法概念與程式流程更直觀。

虛擬碼

function bitonicSort(start, count, direction):
    if count <= 1:
        return
    mid = count / 2
    bitonicSort(start, mid, ASCENDING)
    bitonicSort(start + mid, mid, DESCENDING)
    bitonicMerge(start, count, direction)

function bitonicMerge(start, count, direction):
    if count <= 1:
        return
    k = count / 2
    for i in start .. start + k - 1:
        compareAndSwap(i, i + k, direction)
    bitonicMerge(start, k, direction)
    bitonicMerge(start + k, k, direction)

實際 JavaScript 對照

async function bitonicSort(start, count, direction) {
    if (count <= 1 || !isSorting) return;
    const mid = Math.floor(count / 2);
    await bitonicSort(start, mid, 1);
    await bitonicSort(start + mid, count - mid, 0);
    await bitonicMerge(start, count, direction);
}

async function bitonicMerge(start, count, direction) {
    if (count <= 1 || !isSorting) return;
    const k = Math.floor(count / 2);
    for (let i = start; i < start + k; i++) {
        await compareAndSwap(i, i + k, direction);
    }
    await bitonicMerge(start, k, direction);
    await bitonicMerge(start + k, count - k, direction);
}

程式碼與動畫對應

if (count <= 1 || !isSorting) return;   -> 無須排序或已取消時停止，動畫不再繼續
const mid = Math.floor(count / 2);        -> 計算分割點，準備將區段分為上下兩部份
await bitonicSort(start, mid, 1);         -> 遞迴建立升冪子序列，動畫呈現左側遞迴處理
await bitonicSort(start + mid, count - mid, 0); -> 遞迴建立降冪子序列，動畫呈現右側遞迴處理
await bitonicMerge(start, count, direction); -> 執行合併，動畫開始比較與交換成有序序列
await compareAndSwap(i, i + k, direction); -> 比較成對元素並在動畫中交換位置

邊界條件（Boundary Conditions）