摆动排序
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。要求时间复杂度是O(N)。
示例：
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
思路分析
为了方便说明，我们假定题目中所求的序列为C。
题目中要求摆动排序，也就是说要求元素被排列成 nums[0] < nums[1] > nums[2] < nums[3]…的顺序，试想，如果我们定义一个序列A，它的顺序是这样被定义的：先依次取所有的偶数位，然后依次取所有的奇数位构成一个新的序列。
于是获取到的序列为(注意，我们的下标是从0开始的)：
nums[1],nums[3],nums[5],nums[0],nums[2],nums[4]
示意图如下所示
于是，我们可以这样想，如果这个序列A是从大到小有序的，那么它就一定是一个摆动排序解（读者可以想想为什么），那么我们的问题就转化为对序列A排序。
但我们发现无论哪个排序算法的时间复杂度都达不到O(N)要求，而题目要求时间复杂度是O(N)，这该怎么办呢？
再仔细一想，我们发现其实不需要真正对序列A排序。如果我们将序列A中的数分成2半，其中一半的任意一个数都大于另一半中的任意一个数的话，所构成的序列就基本满足摆动要求。
比如上图中如果序列A被切分为2个子序列，A[0..2]和A[3..5]，且A[0..2]中的任意一个数都大于A[3..5]中任意一个数，则其构成的序列A基本满足摆动要求。
为什么说基本呢？因为这中间还有一个问题需要注意，由于序列A不是严格排序的，在任意一半中存在两个相同的值随机存放的可能，那么如果这两个半的数据量相差较大的话（比如一个的数据量是1，另一个的数据量是9）在序列A还原为序列C的过程中就有可能将两个相同的数挨在一起，这显然是不满足要求的，所以要尽可能让两半的数据量差不多，于是我们想到，可以先找到这个序列的中位数，然后将序列分成小于中位数的、等于中位数的、大于中位数的。如果中位数只有一个，那么一定可以保证小于中位数的数的数量与大于中位数的数的数量相差不大（差值在1以内），可以满足要求；如果中位数有不止一个，那么可以将多余的中位数分给少的那么一边，那么依然可以满足要求。
总结
总结一下思路
首先找到序列中的中位数，将序列分为A1、A2两部分，A1部分的数全部大于中位数，A2部分的数全部小于中位数，于是构造出序列A(A1、中位数、A2)。
接着用序列A构造出答案序列。
代码
void wiggleSort(vector<int>& nums) {
int n = nums.size();
// 找到中位数
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;
// 索引映射关系
#define A(i) nums[(1+2*(i)) % (n|1)]
// 3路快排 in O(n) time with O(1) space.
int i = 0, j = 0, k = n - 1;
while (j <= k) {
if (A(j) > mid)
swap(A(i++), A(j++));
else if (A(j) < mid)
swap(A(j), A(k--));
else
j++;
}
}
参考文章：https://leetcode.com/problems/wiggle-sort-ii/discuss/77677/O(n)+O(1)-after-median-Virtual-Indexing
