排序算法之：波浪排序（Wave Sort）的进阶应用与边界条件处理

题目描述
给定一个无序整数数组，要求将其重新排列成“波浪形”：即对于任意奇数索引 i（0-based），满足 arr[i] >= arr[i-1] 且 arr[i] >= arr[i+1]（如果存在）。例如，输入 [3, 5, 2, 1, 6, 4] 可排列为 [3, 5, 2, 6, 1, 4] 或 [2, 6, 1, 5, 3, 4] 等合法波浪形式。要求时间复杂度为 O(n)，空间复杂度为 O(1)。

解题过程

步骤1：理解波浪形态的数学规律
波浪排序的核心规律是：

• 所有奇数索引位置的值应大于或等于其相邻的偶数索引位置的值（即“波峰”）。
• 不需要整体排序，只需局部调整满足波浪条件即可。

步骤2：贪心策略的可行性分析
通过观察发现，只需确保每个奇数索引 i 的值是相邻三个元素（i-1, i, i+1）中的最大值，即可保证波浪形态。贪心策略：

1. 遍历所有奇数索引 i。
2. 若 arr[i] 小于 arr[i-1]，交换两者。
3. 若 i+1 存在且 arr[i] 小于 arr[i+1]，交换两者。
   此方法可在一次遍历中完成，且交换操作不会破坏已处理部分的波浪性质。

步骤3：具体实现与边界处理

def wave_sort(arr):
    n = len(arr)
    for i in range(0, n, 2):  # 遍历所有偶数索引（等效处理奇数索引的相邻关系）
        if i > 0 and arr[i] < arr[i-1]:
            arr[i], arr[i-1] = arr[i-1], arr[i]
        if i < n-1 and arr[i] < arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]

关键细节：

• 遍历偶数索引可统一处理奇数索引的波峰条件。
• 交换操作需注意数组边界（如首尾元素）。

步骤4：正确性验证
以 [3, 5, 2, 1, 6, 4] 为例：

• i=0：比较 3 和 5，交换为 [5, 3, 2, 1, 6, 4]。
• i=2：比较 2 和 3（左）及 1（右），交换为 [5, 3, 2, 1, 6, 4]（无需变动）。
• i=4：比较 6 和 1（左）及 4（右），交换为 [5, 3, 2, 6, 1, 4]。
  最终得到合法波浪数组。

步骤5：进阶边界场景分析
若数组包含重复元素（如 [2, 2, 2, 1]），贪心策略仍有效：

• 通过交换确保波峰条件，重复元素可能相邻但不会破坏规则（因条件为 >=）。

总结
波浪排序通过局部贪心交换实现 O(n) 时间复杂度，无需全局排序。核心在于利用奇数索引的波峰约束，一次遍历即可完成调整，适用于实时数据流处理等场景。