排序算法之：Brick Sort（砖排序）的并行化特性与边界条件处理 题目描述 Brick Sort（又称奇偶排序，Odd-Even Sort）是一种基于比较的并行排序算法，其核心思想是通过多轮奇偶交替的比较-交换操作，逐步将数组排序。每轮分为两个阶段： 奇数阶段 ：比较所有奇数索引对（(1,2), (3,4), ...） 偶数阶段 ：比较所有偶数索引对（(0,1), (2,3), ...） 重复以上阶段直到数组完全有序。 解题步骤 初始化与循环控制 设置标志位 sorted = false ，表示数组是否已有序。 进入主循环，直到 sorted 为 true 。 奇数阶段处理 将 sorted 设为 true ，假设本轮已有序。 遍历所有奇数索引对（ i = 1, 3, 5, ... ，且 i < n-1 ）： 比较 arr[i] 和 arr[i+1] ，若逆序则交换，并将 sorted 设为 false 。 偶数阶段处理 与奇数阶段类似，但遍历偶数索引对（ i = 0, 2, 4, ... ，且 i < n-1 ）： 比较 arr[i] 和 arr[i+1] ，若逆序则交换，并更新 sorted = false 。 终止条件 若一轮奇数阶段和偶数阶段均未发生交换（ sorted 保持 true ），说明数组已有序，退出循环。 边界条件与优化 数组长度为奇数 ：在偶数阶段，最后一个偶数索引对可能越界（例如 n=5 时索引对为 (4,5)），需通过 i < n-1 限制遍历范围。 并行化特性 ：奇数阶段和偶数阶段内部的所有比较-交换操作均可并行执行，适合多线程或硬件加速。 时间复杂度 ： 最坏情况（完全逆序）需 O(n²) 次比较。 但实际并行优化后，每轮阶段的时间可降至 O(1)（假设足够多的处理器），总轮数最多为 n 轮。 示例 对数组 [5, 2, 9, 1] 排序： 第1轮奇数阶段 ：比较 (2,9) → 有序，不交换； sorted=true 。 第1轮偶数阶段 ：比较 (5,2) → 逆序，交换为 [2,5,9,1] ；比较 (9,1) → 逆序，交换为 [2,5,1,9] ； sorted=false 。 第2轮奇数阶段 ：比较 (5,1) → 逆序，交换为 [2,1,5,9] ； sorted=false 。 第2轮偶数阶段 ：比较 (2,1) → 逆序，交换为 [1,2,5,9] ；比较 (5,9) → 有序； sorted=false 。 第3轮奇数阶段 ：无交换， sorted=true ；偶数阶段无交换，排序完成。 通过奇偶交替的局部排序，最终全局有序性得以保证。