排序算法之：波浪排序（Wave Sort） 题目描述： 给定一个未排序的整数数组，你需要将其重新排列成"波浪形"排序。波浪排序要求数组元素交替排列，使得每个奇数索引（1, 3, 5...）的元素都大于或等于其相邻的两个元素，或者每个偶数索引（0, 2, 4...）的元素都小于或等于其相邻的两个元素。更具体地说，通常要求满足：nums[ 0] <= nums[ 1] >= nums[ 2] <= nums[ 3] >= nums[ 4 ]... 解题过程： 第一步：理解波浪排序的核心要求 波浪排序的核心模式是"小-大-小-大"交替排列。对于索引i： 如果i是偶数，那么nums[ i] <= nums[ i+1 ]（当i+1存在时） 如果i是奇数，那么nums[ i] >= nums[ i+1 ]（当i+1存在时） 第二步：分析问题特点 这个排序不需要完全有序，只需要满足局部的大小关系。我们可以利用这个特点设计更高效的算法。 第三步：选择解题策略 有两种主要方法： 排序后交换法：先排序再调整 一次遍历法：直接通过一次遍历调整位置 第四步：详细讲解排序后交换法 首先对数组进行升序排序 从索引1开始，每隔一个元素与后一个元素交换 具体操作：遍历所有奇数索引位置（1, 3, 5...），将当前元素与后一个元素交换 示例：数组[ 3, 2, 1, 4 ] 排序后：[ 1, 2, 3, 4 ] 交换索引1和2：得到[ 1, 3, 2, 4 ] 验证：1<=3>=2 <=4 ✓ 第五步：详细讲解一次遍历法（更优解） 这种方法不需要完全排序，时间复杂度O(n)： 遍历数组的所有偶数索引位置（0, 2, 4...） 对于每个位置i，检查三个条件： 如果i>0且nums[ i] > nums[ i-1]，交换nums[ i]和nums[ i-1 ] 如果i<n-1且nums[ i] > nums[ i+1]，交换nums[ i]和nums[ i+1 ] 实际上只需要保证每个偶数位置的值都不大于相邻位置即可 第六步：算法正确性证明 通过数学归纳法可以证明，这种方法能保证： 所有偶数位置的值都不大于相邻的奇数位置值 所有奇数位置的值都不小于相邻的偶数位置值 第七步：边界情况处理 空数组或单元素数组：直接返回 双元素数组：需要确保nums[ 0] <= nums[ 1 ] 第八步：复杂度分析 排序交换法：时间复杂度O(nlogn)，空间复杂度O(1)或O(n)（取决于排序算法） 一次遍历法：时间复杂度O(n)，空间复杂度O(1) 这种排序在信号处理、图形学中有实际应用，特别是在需要交替峰值和谷值的可视化场景中。