摘要

摆动排序听起来像在跳舞，实际上它确实是让数组的数字“上下起伏”。我们要把一个整数数组重新排列，满足 nums[0] < nums[1] > nums[2] < nums[3]... 这种交错顺序。这篇文章会用 Swift 带你从头撸清楚摆动排序背后的技巧，包括排序、分组、巧妙插入的实战过程。

描述

题目要求我们把一个数组 nums 改造成如下的交错结构：

nums[0] < nums[1] > nums[2] < nums[3] ...

这个结构的关键点是：

• 奇数下标元素大于相邻的偶数下标元素。
• 偶数下标元素小于相邻的奇数下标元素。

可以认为是局部波峰波谷结构：小、大、小、大……

你不需要返回新的数组，而是直接修改原数组即可。

题解答案

我们可以先对数组排序，然后将较小的数填在偶数位，较大的数填在奇数位。

这个策略保证了交错关系。重点是我们要“倒着”填充数组，避免相邻重复值打破摆动规则。

题解代码（Swift）

func wiggleSort(_ nums: inout [Int]) {let sorted = nums.sorted()let n = nums.countvar left = (n - 1) / 2var right = n - 1for i in 0..<n {if i % 2 == 0 {nums[i] = sorted[left]left -= 1} else {nums[i] = sorted[right]right -= 1}}
}

题解代码分析

步骤一：排序数组

let sorted = nums.sorted()

我们先排序一遍数组，这样方便从中间拆成两个部分。

步骤二：左右指针分段

var left = (n - 1) / 2  // 前半部分的最大索引（用于偶数位）
var right = n - 1       // 后半部分的最大索引（用于奇数位）

这个拆法保证了我们从中间往前、往后取值，不会让重复数字挤在一起。

步骤三：按位置交错插入

for i in 0..<n {if i % 2 == 0 {nums[i] = sorted[left]left -= 1} else {nums[i] = sorted[right]right -= 1}
}

• 偶数位：从左半部分最大往前取（最小值）
• 奇数位：从右半部分最大往前取（最大值）

最终形成“小大小大”这样的节奏排序。

示例测试及结果

示例 1

var nums1 = [1, 5, 1, 1, 6, 4]
wiggleSort(&nums1)
print(nums1)  // 输出如：[1,6,1,5,1,4] 或类似交错结构

示例 2

var nums2 = [1, 3, 2, 2, 3, 1]
wiggleSort(&nums2)
print(nums2)  // 输出如：[2,3,1,3,1,2]

示例 3（边界情况）

var nums3 = [1]
wiggleSort(&nums3)
print(nums3)  // 输出：[1]

时间复杂度分析

• 排序：O(n log n)
• 重排：O(n)
• 总时间复杂度：O(n log n)

空间复杂度分析

• 我们使用了一个额外的排序数组 sorted，空间为 O(n)
• 总空间复杂度：O(n)（如果原地排序并三指针替换，可降到 O(1)）

总结

“摆动排序”这题不只是让数字跳个舞，更是考验我们如何拆分数组、如何巧妙插入。

你需要掌握的几个重点：

• 排序 + 分段思维
• 左右指针从两端交替插入
• 巧妙处理重复值，避免打破排序节奏