如何用Ruby实现满足arr[0]<=arr[1]>=arr[2]…规则的数组波形排序

要实现符合arr[0] <= arr[1] >= arr[2] <= arr[3]……规则的波形数组，有两种实用的Ruby实现方式，下面分别说明：

方法一：排序后交换相邻元素 #

思路 #

先将数组排序，再从索引1开始，每隔一个位置交换当前元素和下一个元素。排序后的数组本身是递增的，交换后能快速形成“小-大-小-大”的波形结构。

代码实现 #

def wave_sort(arr)
  sorted_arr = arr.sort
  # 从索引1开始，步长为2遍历，交换当前元素与下一个元素
  (1...sorted_arr.length).step(2) do |i|
    sorted_arr[i], sorted_arr[i+1] = sorted_arr[i+1], sorted_arr[i] if i+1 < sorted_arr.length
  end
  sorted_arr
end

# 测试示例输入
input = [2, 1, 5, 3, 11, 7]
puts wave_sort(input).inspect # 输出示例：[1, 3, 2, 7, 5, 11]（满足波形规则）

方法二：单次遍历直接调整 #

思路 #

遍历数组，针对每个位置的奇偶性（索引从0开始）直接调整相邻元素：

• 奇数索引（1、3、5...）：需要满足当前元素 >= 前一个元素，不满足则交换两者
• 偶数索引（2、4、6...）：需要满足当前元素 <= 前一个元素，不满足则交换两者

这种方法不需要预先排序，时间复杂度为O(n)，效率更高。

代码实现 #

def wave_sort(arr)
  arr.each_index do |i|
    next if i.zero? # 跳过第一个元素，无需比较
    
    if i.odd?
      # 奇数索引需作为峰值，若小于前一个元素则交换
      arr[i], arr[i-1] = arr[i-1], arr[i] if arr[i] < arr[i-1]
    else
      # 偶数索引需作为谷值，若大于前一个元素则交换
      arr[i], arr[i-1] = arr[i-1], arr[i] if arr[i] > arr[i-1]
    end
  end
  arr
end

# 测试示例输入
input = [2, 1, 5, 3, 11, 7]
puts wave_sort(input).inspect # 输出示例：[2, 5, 1, 11, 3, 7]（满足波形规则）

注意事项 #

波形数组的结果并不唯一，只要符合arr[0] <= arr[1] >= arr[2] <= arr[3]……的规则，任何输出都是正确的，题目给出的[2,7,3,11,1,5]也是合法的结果之一。

内容的提问来源于stack exchange，提问作者Arish Khan