Java 奇偶排序演算法完整實作與原理圖解

演算法簡介

奇偶排序 是一種平行化排序演算法，核心思想：交替對奇數索引對與偶數索引對進行比較交換，直到陣列完全有序。因其操作獨立，適合多核心平行處理。

執行流程圖解

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

第 1 趟：比較奇數索引對 (索引 0&1, 2&3, 4&5)

初始: [6, 2, 4, 1, 5, 9]
比較: (6,2) (4,1) (5,9)
交換: [2, 6, 1, 4, 5, 9]

第 2 趟：比較偶數索引對 (索引 1&2, 3&4)

輸入: [2, 6, 1, 4, 5, 9]
比較: (6,1) (4,5)
交換: [2, 1, 6, 4, 5, 9]

第 3 趟：比較奇數索引對

輸入: [2, 1, 6, 4, 5, 9]
比較: (2,1) (6,4) (5,9)
交換: [1, 2, 4, 6, 5, 9]

第 4 趟：比較偶數索引對

輸入: [1, 2, 4, 6, 5, 9]
比較: (2,4) (6,5)
交換: [1, 2, 4, 5, 6, 9]  ← 已排序完成

Java 完整實作

public class OddEvenSort {

    public static void oddEvenSort(int[] numbers) {
        int temp;
        // 外層控制趟數，最多需 n-1 趟
        for (int i = numbers.length - 1; i > numbers.length / 2 - 1; i--) {
            // 奇數索引對比較 (1&2, 3&4, 5&6...)
            for (int j = 1; j <= i; j += 2) {
                if (j == numbers.length - 1) break; // 避免越界
                if (numbers[j] > numbers[j + 1]) {
                    temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
            // 偶數索引對比較 (0&1, 2&3, 4&5...)
            for (int j = 0; j <= i; j += 2) {
                if (j == numbers.length - 1) break;
                if (numbers[j] > numbers[j + 1]) {
                    temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {12, 33, 45, 33, 13, 55, 34, 7, 6};
        oddEvenSort(numbers);
        for (int num : numbers) {
            System.out.print(num + " ");
        }
        // 輸出: 6 7 12 13 33 33 34 45 55
    }
}

複雜度分析

• 時間複雜度：O(n²) - 最壞、平均情況；O(n) - 最佳情況 (已排序)
• 空間複雜度：O(1) - 原地排序
• 穩定性：穩定排序 (相等元素不交換位置)

適用場景

雖然單執行緒效能不如快速排序，但奇偶排序的比較操作互不相干，極易平行化。在多核心 GPU 或分散式環境中，可顯著縮短排序時間，是平行計算教學經典案例。