【一、项目背景详细介绍】

排序算法是计算机科学中最基础也是最重要的组成部分之一。从简单的冒泡排序、插入排序，到高效的快速排序、归并排序，各种算法在不同场景下各有优劣。奇偶排序（Odd-Even Sort），也称砖排序（Brick Sort），是一种基于并行比较与交换思想的排序算法。算法通过交替执行奇偶索引间和偶奇索引间的比较交换，实现最终的有序排列。虽然其时间复杂度为O(n^2)，但由于每轮比较并交换过程可以并行化，在多处理器或并行计算环境下有一定优势，并且算法实现思路简单，常用于并行计算实验与教学场景。

【二、项目需求详细介绍】

1. 功能需求

   • 在Java环境中实现Odd-Even Sort算法，能够对整数数组和可比较对象数组进行正序和逆序排序。

   • 提供可选的并行化接口（使用Java并发包实现），以模拟并行执行奇偶交换步骤。

2. 性能需求

   • 正常情况下时间复杂度为O(n^2)，在多线程环境下，应利用线程池并行比较交换，缩短执行时间。

   • 额外空间复杂度为O(1)，需在原地完成交换。

3. 代码质量需求

   • 方法职责单一，分为奇偶轮比较、主排序流程、泛型支持、并行化可选等模块。

   • 完整注释关键步骤，说明算法原理与并行化实现要点。

   • 提供JUnit单元测试，覆盖普通场景、重复元素、空数组等边界情况。

【三、相关技术详细介绍】

1. Java数组与泛型

   • 使用原生数组存储基本类型或对象引用，泛型方法支持任意实现Comparable接口的类型。

2. 奇偶轮比较思想

   • 算法交替执行两种比较模式：奇轮比较索引对(1,2),(3,4)...；偶轮比较索引对(0,1),(2,3)...

   • 每轮遍历后保证相邻对调整部分有序，经过足够轮次后，数组整体有序。

3. 并发编程（可选）

   • 使用Java ExecutorService创建固定线程池，对每轮内的各个比较任务并行提交和同步等待。

4. 并行与同步

   • 通过CountDownLatch或CyclicBarrier实现每轮比较交换完成后再进入下一轮，保证数据一致性。

【四、实现思路详细介绍】

1. 主流程

   • 设定isSorted=false；

   • 当isSorted=false时，执行以下两步，并在每步中更新isSorted状态：
     a) 奇轮：遍历所有奇数索引i=1; i<n-1; i+=2，比较并交换arr[i]与arr[i+1]；
     b) 偶轮：遍历所有偶数索引i=0; i<n-1; i+=2，比较并交换arr[i]与arr[i+1]；

   • 若在一整轮（奇+偶）中未发生任何交换，则退出循环，排序完成。

2. 泛型支持

   • 方法签名使用<T extends Comparable<T>>，比较时使用compareTo并根据ascending切换方向。

3. 并行化实现（可选）

   • 每轮奇或偶比较操作可封装为独立任务，提交到线程池执行。

   • 使用CyclicBarrier等待该轮所有任务完成后再进入下一步。

4. 优化策略

   • 在单线程环境下，当执行完成一轮未交换时即可提早终止，最坏轮次为n次。

【五、完整实现代码】

// 文件：OddEvenSort.java
// 描述：Odd-Even Sort（奇偶排序）实现，支持泛型、正/逆序及可选并行化

import java.util.Arrays;
import java.util.concurrent.*;

public class OddEvenSort {

    /**
     * 单线程版本：奇偶排序
     */
    public static <T extends Comparable<T>> void oddEvenSort(T[] arr, boolean ascending) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        boolean isSorted = false;
        while (!isSorted) {
            isSorted = true;
            // 奇轮
            for (int i = 1; i < n - 0; i += 2) {
                if (compareAndSwap(arr, i, ascending)) {
                    isSorted = false;
                }
            }
            // 偶轮
            for (int i = 0; i < n - 1; i += 2) {
                if (compareAndSwap(arr, i, ascending)) {
                    isSorted = false;
                }
            }
        }
    }

    /**
     * 并行化版本：奇偶排序
     */
    public static <T extends Comparable<T>> void oddEvenSortParallel(T[] arr, boolean ascending, int threadCount) throwsInterruptedException {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        ExecutorService pool = Executors.newFixedThreadPool(threadCount);
        CyclicBarrier barrier = new CyclicBarrier(threadCount, () -> {});
        boolean isSorted = false;
        while (!isSorted) {
            isSorted = true;
            // 提交奇轮任务
            int tasks = threadCount;
            int chunk = (n + tasks - 1) / tasks;
            for (int t = 0; t < tasks; t++) {
                final int start = 1 + t * chunk * 2;
                final int end = Math.min(n - 1, start + chunk * 2 - 2);
                pool.submit(() -> {
                    for (int i = start; i <= end; i += 2) {
                        if (compareAndSwap(arr, i, ascending)) {
                            isSorted = false;
                        }
                    }
                    barrier.await();
                });
            }
            barrier.await();
            // 偶轮同理
            for (int t = 0; t < tasks; t++) {
                final int start = t * chunk * 2;
                final int end = Math.min(n - 1, start + chunk * 2 - 2);
                pool.submit(() -> {
                    for (int i = start; i <= end; i += 2) {
                        if (compareAndSwap(arr, i, ascending)) {
                            isSorted = false;
                        }
                    }
                    barrier.await();
                });
            }
            barrier.await();
        }
        pool.shutdown();
    }

    /**
     * 比较并交换，如果交换则返回true
     */
    private static <T extends Comparable<T>> boolean compareAndSwap(T[] arr, int i, boolean asc) {
        int j = i + 1;
        if (j >= arr.length) return false;
        boolean condition = asc ? arr[i].compareTo(arr[j]) > 0 : arr[i].compareTo(arr[j]) < 0;
        if (condition) {
            T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            return true;
        }
        return false;
    }

    /**
     * 简单测试
     */
    public static void main(String[] args) throws Exception {
        Integer[] data = {5,2,9,1,5,6};
        System.out.println("原始：" + Arrays.toString(data));
        oddEvenSort(data, true);
        System.out.println("单线程正序：" + Arrays.toString(data));
        Integer[] data2 = {5,2,9,1,5,6};
        oddEvenSortParallel(data2, true, 4);
        System.out.println("并行正序：" + Arrays.toString(data2));
    }
}

【六、代码详细解读】

• oddEvenSort：单线程实现，通过奇偶轮交替比较交换，实现原地排序；

• oddEvenSortParallel：并行版本，利用ExecutorService和CyclicBarrier将比较任务分配给多个线程，模拟并行交换；

• compareAndSwap：根据排序方向判断并交换相邻元素，返回是否发生交换；

• main：展示单线程与并行版本的排序效果。

【七、项目详细总结】

Odd-Even Sort通过交替奇轮和偶轮的比较交换，最终实现数组有序。算法本质是冒泡排序的并行化变种，时间复杂度为O(n^2)，但可通过多线程实现局部并行，提高在并发环境下的性能。该算法易于理解，原地完成，无额外大规模空间开销，在并行计算与教学实验中有一定价值。

【八、项目常见问题及解答】

1. 问：与冒泡排序有什么区别？
   答：冒泡排序每轮依次比较(0,1),(1,2),(2,3)...，而奇偶排序将此过程分为奇轮和偶轮，可并行执行；

2. 问：并行化效果如何？
   答：对于大规模数据和多核环境，并行版本能显著降低单轮执行时间，但需考虑线程开销和同步延迟；

3. 问：如何判断终止？
   答：当一整轮（奇+偶）比较中未发生任何交换时，可提前结束。

【九、扩展方向与性能优化】

1. 分段并行：对数组划分多个独立区块并行执行奇偶排序，最后再合并有序块；

2. 融合其他算法：对小区间切换插入排序或快速排序，提高常数性能；

3. GPU加速：利用CUDA或OpenCL将比较过程提交到GPU上，并行度更高；

4. 改进同步机制：使用更轻量级的栅栏或无锁数据结构减少同步开销。