奇偶排序（Odd-Even Sort） 题目描述 给定一个整数数组，使用奇偶排序算法将其按升序排列。奇偶排序是一种基于冒泡排序的并行排序算法，通过多轮操作完成排序：在每一轮中，分别对数组中奇数索引对（第1个与第2个、第3个与第4个…）和偶数索引对（第0个与第1个、第2个与第3个…）进行比较和交换，直到整个数组有序。 解题过程 1. 算法核心思想 奇偶排序将排序过程分为两个重复执行的阶段： 奇数阶段 ：比较所有奇数索引对 (arr[1]和arr[2]) 、 (arr[3]和arr[4]) 、 (arr[5]和arr[6]) …，若前者大于后者则交换。 偶数阶段 ：比较所有偶数索引对 (arr[0]和arr[1]) 、 (arr[2]和arr[3]) 、 (arr[4]和arr[5]) …，若前者大于后者则交换。 重复交替执行这两个阶段，直到某一轮中没有发生任何交换，说明数组已有序。 2. 逐步演示 以数组 [5, 2, 9, 1, 5, 6] 为例： 初始状态 ： [5, 2, 9, 1, 5, 6] 第1轮偶数阶段 （比较索引对 (0,1)、(2,3)、(4,5)）： (0,1): 5>2 → 交换 → [2, 5, 9, 1, 5, 6] (2,3): 9>1 → 交换 → [2, 5, 1, 9, 5, 6] (4,5): 5 <6 → 不交换 第1轮奇数阶段 （比较索引对 (1,2)、(3,4)）： (1,2): 5>1 → 交换 → [2, 1, 5, 9, 5, 6] (3,4): 9>5 → 交换 → [2, 1, 5, 5, 9, 6] 第2轮偶数阶段 （比较索引对 (0,1)、(2,3)、(4,5)）： (0,1): 2>1 → 交换 → [1, 2, 5, 5, 9, 6] (2,3): 5=5 → 不交换 (4,5): 9>6 → 交换 → [1, 2, 5, 5, 6, 9] 第2轮奇数阶段 （比较索引对 (1,2)、(3,4)）： (1,2): 2 <5 → 不交换 (3,4): 5 <6 → 不交换 本轮无交换，排序完成。 3. 算法实现要点 使用一个标志位 sorted 记录是否发生交换。 循环执行以下步骤直到 sorted 为真： 设置 sorted = true 偶数阶段 ：遍历索引 i = 0, 2, 4… （每次+2），比较 arr[i] 和 arr[i+1] ，若逆序则交换并设置 sorted = false 奇数阶段 ：遍历索引 i = 1, 3, 5… （每次+2），比较 arr[i] 和 arr[i+1] ，若逆序则交换并设置 sorted = false 4. 复杂度分析 时间复杂度：最坏情况 O(n²)，但优于普通冒泡排序的常数因子（因并行潜力）。 空间复杂度：O(1)，原地排序。 总结 奇偶排序通过交替的奇偶阶段比较相邻元素，逐步将较大元素“浮”到右侧。其结构适合并行计算，但在单线程中效率与冒泡排序类似。