Skip to content
280. 摆动排序
概述
给定一个无序数组 nums，将其原地重新排列，使得序列满足以下摆动条件：
- 偶数下标（0、2、4 …）处的值 ≤ 相邻元素
- 奇数下标（1、3、5 …）处的值 ≥ 相邻元素
即 nums[0] ≤ nums[1] ≥ nums[2] ≤ nums[3] …。
允许相邻元素相等，不需要输出所有可能结果，只需返回任意一个满足条件的排列。
基本概念
摆动排序只约束了相邻元素之间的大小关系，并不要求全局有序。相比“严格摆动”（如 324 题），这里允许相等，处理上更宽松。
工作原理
算法采用一趟贪心扫描：
- 遍历
i从0到n-2。 - 若
i为偶数且nums[i] > nums[i + 1]，交换两者。 - 若
i为奇数且nums[i] < nums[i + 1]，交换两者。
这样一趟扫描下来，即可保证整个数组满足摆动条件。
局部交换不会破坏已处理前缀的约束。
以偶数下标为例：假设前两个元素已经满足 nums[0] ≤ nums[1]。处理 i = 1 时，要求 nums[1] ≥ nums[2]。若 nums[1] < nums[2]，交换得到 nums'[1] = 原nums[2]，nums'[2] = 原nums[1]。由于 nums[0] ≤ 原nums[1] < 原nums[2] = nums'[1]，故 nums[0] ≤ nums'[1] 依然成立。奇数下标情况对称。
因此，每一步交换只改善当前位置，不会破坏前序约束。
示例
Node.js（TypeScript）
ts
/**
* 原地修改数组，使满足 nums[0] <= nums[1] >= nums[2] <= nums[3] ...
*/
function wiggleSort(nums: number[]): void {
for (let i = 0; i < nums.length - 1; i++) {
if (
(i % 2 === 0 && nums[i] > nums[i + 1]) ||
(i % 2 === 1 && nums[i] < nums[i + 1])
) {
[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
}
}
}Java
java
public void wiggleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if ((i % 2 == 0 && nums[i] > nums[i + 1]) ||
(i % 2 == 1 && nums[i] < nums[i + 1])) {
int tmp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = tmp;
}
}
}Python
python
def wiggleSort(nums):
for i in range(len(nums) - 1):
if (i % 2 == 0 and nums[i] > nums[i + 1]) or \
(i % 2 == 1 and nums[i] < nums[i + 1]):
nums[i], nums[i + 1] = nums[i + 1], nums[i]示例 1
输入: [3, 5, 2, 1, 6, 4]
过程:
i=0 (偶): 3 <= 5 满足
i=1 (奇): 5 >= 2 满足
i=2 (偶): 2 > 1 交换 → [3,5,1,2,6,4]
i=3 (奇): 2 < 6 交换 → [3,5,1,6,2,4]
i=4 (偶): 2 <= 4 满足
输出: [3,5,1,6,2,4] (满足条件)示例 2
长度 ≤ 1 直接返回，无需处理。
输入: []
输出: []
输入: [42]
输出: [42]示例 3
大量相等元素：
输入: [2,2,2,2,2]
过程:
i=0: 2 <= 2
i=1: 2 >= 2
i=2: 2 <= 2
i=3: 2 >= 2
输出: [2,2,2,2,2] 满足条件示例 4
严格递减：
输入: [5,4,3,2,1]
过程:
i=0 (偶): 5 > 4 交换 → [4,5,3,2,1]
i=1 (奇): 5 >= 3 满足
i=2 (偶): 3 > 2 交换 → [4,5,2,3,1]
i=3 (奇): 3 >= 1 满足
输出: [4,5,2,3,1] 满足条件注意点
- 允许相等：题目不要求严格大于或小于，相邻元素相等依然合法。这简化了实现，使得一趟贪心即可解决。
- 原地修改：函数不得返回新数组，只能修改传入的数组。
- 复杂度：时间 O(n)，空间 O(1)。题目的难点不在复杂度，而在证明局部交换策略不会破坏已完成前缀的正确性。
- 结果不唯一：满足条件的排列可能有多个，返回任意一个即可。
与 324. 摆动排序 II 的区别
- 280 题允许相邻相等，解法简单，O(n) 时间 O(1) 空间。
- 324 题要求严格交替，不允许相等元素相邻，元素顺序为
nums[0] < nums[1] > nums[2] < nums[3] ...。通常需要先排序再按照特定模式交错放置，复杂度 O(n log n) 且需要额外空间。