奇偶排序算法原理與 Java 實作詳解

算法思想

奇偶排序 是冒泡排序的平行化變體，又稱 Brick Sort。核心邏輯：奇數輪比較奇數索引與其相鄰偶數索引，偶數輪比較偶數索引與其相鄰奇數索引，交替進行直到無交換發生。

執行流程圖解

陣列：[6, 2, 4, 1, 5, 9]

1. 奇數輪：比較 (0,1)、(2,3)、(4,5) → [2, 6, 1, 4, 5, 9]
2. 偶數輪：比較 (1,2)、(3,4) → [2, 1, 6, 4, 5, 9]
3. 奇數輪：比較 (0,1)、(2,3)、(4,5) → [1, 2, 4, 6, 5, 9]
4. 偶數輪：比較 (1,2)、(3,4) → [1, 2, 4, 5, 6, 9]
5. 無交換，排序完成。

Java 完整實作

public class OddEvenSort {
    public static void sort(int[] arr) {
        boolean sorted = false;
        while (!sorted) {
            sorted = true;
            // 奇數輪：索引 0,2,4... 與右鄰比較
            for (int i = 0; i < arr.length - 1; i += 2) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    sorted = false;
                }
            }
            // 偶數輪：索引 1,3,5... 與右鄰比較
            for (int i = 1; i < arr.length - 1; i += 2) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    sorted = false;
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

複雜度分析

• 時間複雜度：最壞 O(n²)，最好 O(n)（已排序），平均 O(n²)。
• 空間複雜度：O(1) 原地排序。
• 穩定性：穩定（相等元素不交換）。
• 並行化潛力：奇/偶輪內部比較互不干擾，極適合多核並行或 GPU 實作。

適用場景

• 教學展示平行排序概念。
• 硬體層面（FPGA/GPU）排序網路實作。
• 小規模、近乎有序資料集（最好情況接近 O(n)）。