波浪排序（Wave Sort）的进阶优化与边界条件处理

波浪排序是一种特殊的排序算法，它将数组排列成“波浪”形状，即：对于排序后的数组，有 arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] ... 以此类推。这个问题不仅是实现一种特定排列，也常用来考察对数组元素顺序的高效调整能力。进阶优化关注如何在线性时间内完成，并准确处理各种边界条件。

题目描述

给定一个未排序的整数数组，请将其重新排列成波浪形。具体要求如下：

1. arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] ...
2. 若有多种可能的波浪形式，任何一种都算正确。
3. 尽量在线性时间复杂度 O(n) 内完成，且只使用常数级别的额外空间（原地修改）。

解题过程

步骤1：理解波浪条件

波浪条件可以分奇偶索引位置来看：

• 对于偶数索引 i (0, 2, 4, ...)，应满足 arr[i] >= arr[i+1]（注意 i+1 不能越界）。
• 对于奇数索引 i (1, 3, 5, ...)，应满足 arr[i] <= arr[i+1]（注意 i+1 不能越界）。

但更直观的思考是：只要数组中每个“峰”的位置（即偶数索引）都比它相邻的“谷”大，就满足条件。这给了我们操作空间。

步骤2：基础思路——排序后调整

最直观的方法：

1. 先对数组进行排序（例如快速排序，O(n log n)）。
2. 然后从头开始，将每两个相邻元素交换，从索引1开始交换（即交换 (1,2), (3,4), (5,6)...）。
   • 排序后数组是有序递增的，交换后就会形成：小，大，小，大... 的模式，这恰好满足 arr[0] <= arr[1] >= arr[2] <= arr[3] ...
   • 注意，这与我们定义的波浪（arr[0] >= arr[1] ...）正好相反。要解决，可以从索引0开始交换（交换 (0,1), (2,3), (4,5)...），或者先反转排序顺序（降序）。

这种方法简单，但时间复杂度是 O(n log n)，空间复杂度通常是 O(log n) 或 O(n)（取决于排序算法）。不满足 O(n) 的要求。

步骤3：进阶优化——一次遍历调整

目标是 O(n) 时间。核心观察是：我们并不需要数组完全有序，只需要局部满足波浪关系即可。

我们可以遍历数组，只关注当前元素和它应该满足的关系：

• 对于偶数索引 i，需要 arr[i] >= arr[i-1]（如果 i>0） 且 arr[i] >= arr[i+1]（如果 i+1 存在）。
• 对于奇数索引 i，需要 arr[i] <= arr[i-1] 且 arr[i] <= arr[i+1]。

但实现时，更简单的方法是只关注相邻三个元素的局部关系。思路如下：

1. 从索引 i=0 开始遍历到 n-1。
2. 对于每个位置 i，检查它和下一个位置 i+1 的关系是否符合当前索引奇偶性要求的波浪条件。如果不符合，就交换 arr[i] 和 arr[i+1]。

但这样逐个检查会遇到问题，因为交换后可能破坏前一个位置的关系。因此，我们需要一个能保证交换后不破坏前面关系的策略。

更稳健的线性算法：
我们可以分奇偶位置单独处理，但有一种更聪明的单次遍历方法：

• 对于偶数位置 i（0, 2, 4...），它应该是“峰”（比相邻的大）。
• 对于奇数位置 i（1, 3, 5...），它应该是“谷”（比相邻的小）。

算法步骤：

1. 从 i=0 遍历到 n-2（因为每次要看 i 和 i+1）。
2. 如果 i 是偶数：
   • 检查是否 arr[i] < arr[i+1]。如果是，则交换 arr[i] 和 arr[i+1]。因为偶数位置应该是峰，应该比下一个大。
3. 如果 i 是奇数：
   • 检查是否 arr[i] > arr[i+1]。如果是，则交换 arr[i] 和 arr[i+1]。因为奇数位置应该是谷，应该比下一个小。

为什么这个算法是 O(n) 且正确的？

• 每次只比较相邻两个元素，时间复杂度 O(n)。
• 对于偶数位置 i，交换 arr[i] 和 arr[i+1] 后，arr[i] 变成了原来较大的数，这保证了 arr[i] >= arr[i+1]。同时，交换可能会影响前一个位置 i-1（奇数位置）的关系吗？我们来看：
  • 如果 i 是偶数，那么 i-1 是奇数。在之前的步骤中，我们已经保证了 arr[i-1] <= arr[i]（原来的值）。交换后，arr[i] 变大了（因为 arr[i] < arr[i+1] 才交换，新 arr[i] 是原来的 arr[i+1]，更大），所以 arr[i-1] <= 新 arr[i] 仍然成立，因为 arr[i-1] <= 旧 arr[i] <= 新 arr[i]。所以前面关系不会破坏。
• 类似地，对于奇数位置 i 的交换，也不会破坏前面偶数位置的关系。

步骤4：边界条件处理

1. 数组长度为 0 或 1：直接返回，无需处理。
2. 遍历到倒数第二个元素：因为每次比较 i 和 i+1，所以 i 最大为 n-2，避免数组越界。
3. 相等元素处理：如果 arr[i] == arr[i+1]，根据算法，不会交换（因为条件用 > 或 <，不包括等于）。这不会破坏波浪条件，因为等于也满足 >= 或 <= 的关系。所以没问题。
4. 奇偶性判断：用 i % 2 == 0 判断偶数索引。

步骤5：实例演示

以数组 [3, 5, 2, 1, 6, 4] 为例：

• n=6，遍历 i 从 0 到 4。
• i=0（偶数）：检查 3 < 5？是，交换 → [5, 3, 2, 1, 6, 4]
• i=1（奇数）：检查 3 > 2？是，交换 → [5, 2, 3, 1, 6, 4]
• i=2（偶数）：检查 3 < 1？否，不交换
• i=3（奇数）：检查 1 > 6？否，不交换
• i=4（偶数）：检查 6 < 4？否，不交换
  结果：[5, 2, 3, 1, 6, 4]，检查波浪：5>=2, 2<=3, 3>=1, 1<=6, 6>=4 ✅

步骤6：代码实现（Python）

def wave_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        if i % 2 == 0:  # 偶数索引应为峰
            if arr[i] < arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        else:  # 奇数索引应为谷
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
    return arr

步骤7：复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(1)，原地交换。

步骤8：进阶讨论

1. 稳定性：波浪排序不关心相同元素的相对顺序，所以不存在稳定性问题。
2. 多种结果：由于交换条件的选择（例如，相等时不交换），算法可能产生不同的有效波浪数组，这都是允许的。
3. 与“排序”的关系：波浪排序并不是完全排序，而是一种特殊的排列。它可用于信号处理、近似排序等场景。

这个算法通过巧妙的局部交换规则，在 O(n) 时间内完成了波浪形排列，并正确处理了边界，是一种高效的实现。