324. Wiggle Sort II的题目大意为：
给你n个无序的数nums, 让你输出如下的顺序: nums[0] < nums[1] > nums[2] < nums[3]….
并且希望算法是O(n)的时间复杂度，O(1)的额外空间复杂度。
初看这道题，没有什么思路，我想了很长时间。后来发现，如果能将数组nums分成两部分，第一部分为{nums[0], nums[2], …}，第二部分为{nums[1], nums[3], …}，且第一部分的数都小于第二部分。那么就可以满足题目的要求顺序了。
将数组分成两部分，可以用获得第K大的数算法（即快排只对一半的元素递归），时间复杂度是O(n)。这样得到一个数组，前n/2的数都小于后n/2的数，再将其分别移动到对应的偶数位和奇数位上去。
照此思路写好程序，发现不AC,原来数组中的数可能会重复。如果数组中第n/2大的数重复多个，那么这些数可能被分到第一个区间，也可能被分到第二个区间，这样对其作移动之后，可能两个相同的数是相邻的，不能满足顺序要求。
大神的答案
后来参考Discuss中大神的解答。
基本思路如下:
1.先找出第 n/2 大的数，设其为pivot。 时间复杂度O(n).
2.对数组遍历一次，将数组三分，小于pivot放在前面，等于pivot放在中间，大于pivot放在后面。
三分像是变形的快排，可以参考荷兰国旗问题。
3.小于pivot的数要移动到 {nums[0], nums[2], nums[4], …}等偶数位上，且尽量放在后面。大于pivot的数移动到{nums[1], nums[3], ..}等奇数位上，且尽量放在前面。剩下的位置放等于pivot的数，位于偶数位小的下标和奇数位大的下标，这样等于pivot的数就不会相邻了。
Step.3可以和Step.2合为一步，原作者使用了一个宏:1
#define>A(i) nums[(1+2*(i)) % (n|1)]
(n | 1)的含义为:1
2if(!(n % 2))
n = n + 1;
这样对应关系为:
A(0) : nums[1].
A(1) : nums[3].
A(2) : nums[5].
A(3) : nums[7].
A(4) : nums[9].
A(5) : nums[0].
A(6) : nums[2].
A(7) : nums[4].
A(8) : nums[6].
A(9) : nums[8].
在实现Step.2的代码时，就将大于pivot的数放A的前部，等于放中间，小于放后面。非常巧妙的完成了分别移动到奇数位、偶数位，并且将等于pivot的数尽量错开。
在实现代码时，我发现STL中找到n大的函数nth_element要比自己实现的快。查看源码， nth_element是这样实现的：
1.数组长度 < 3，采用插入排序的思想。长度 > 3，采用快速排序artition的思想。
2.artition时，pivot选择首元素、尾元素、中间元素的中值。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35cass Solution{
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
// Finda medan.
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int pivot = *midptr;
// if even number: ase = n + 1; else ase = n
int ase = n | 1;
#define>A(i) nums[((i) * 2 + 1) % ase]
int low = 0;
int mid = 0;
int high = n - 1;
while(mid <= high)
{
if>A(mid) > pivot)
{
sap>A(mid++),>A(low++));
}
else if>A(mid) < pivot)
{
sap>A(mid),>A(high--));
}
else
{
mid++;
}
}
}
};