Java 排序算法：奇偶排序（Batcher Odd-Even Sort）原理與實現

算法簡介

奇偶排序，又稱奇偶換位排序或磚排序，是一種簡單的比較排序，最初設計用於並行計算環境。其核心思想：交替對「奇-偶」索引對和「偶-奇」索引對進行比較交換，直到有序。

算法流程

1. 奇數階段：比較索引 (1,2)、(3,4)、(5,6)... 若前者大於後者則交換。
2. 偶數階段：比較索引 (0,1)、(2,3)、(4,5)... 同樣交換。
3. 重複上述兩階段，直到某一輪無任何交換發生，說明已有序。

並行計算優勢

在並行架構中，每個處理器持有數組一個元素，奇數階段所有奇數索引處理器同時與右鄰比較交換，偶數階段偶數索引處理器同時操作，實現高併發。Baudet-Stevenson 算法進一步擴展到每處理器持有子數組的情況。

相關變體：Batcher 奇偶合併排序

Batcher 奇偶合併排序結合比較-交換與完美洗牌操作，在全互連並行機器上效率更高，是經典並行排序網絡之一。

複雜度分析

• 最壞時間複雜度：Θ(n²)
• 空間複雜度：O(1) 原地排序
• 穩定性：穩定（相等元素不交換）

Java 完整實現

package com.baobaotao.test;

public class Sort {

    /** 奇偶排序 */
    public static void batcherSort(int[] array) {
        int length = array.length;
        boolean swapped;
        do {
            swapped = false;
            // 奇數階段: 索引 1,3,5...
            for (int i = 1; i < length - 1; i += 2) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    swapped = true;
                }
            }
            // 偶數階段: 索引 0,2,4...
            for (int i = 0; i < length - 1; i += 2) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    swapped = true;
                }
            }
            printArr(array); // 觀察每輪變化
        } while (swapped);
    }

    /** 交換輔助方法 */
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /** 打印數組 */
    public static void printArr(int[] array) {
        for (int v : array) System.out.print(v + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] number = {11, 95, 45, 15, 78, 84, 51, 24, 12};
        batcherSort(number);
    }
}

運行輸出示例

11 45 15 95 51 78 12 84 24
11 15 45 51 12 95 24 78 84
11 15 12 45 24 51 78 95 84
11 12 15 24 45 51 78 84 95

總結

奇偶排序雖然順序實現效率一般（O(n²)），但其並行特性使其在特定硬體架構（GPU、FPGA、多核集群）上極具價值。理解該算法有助於掌握並行排序網絡的基本構建塊。