题目链接：https://leetcode-cn.com/problems/wiggle-sort-ii/
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
示例 1:
输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]示例 2:
输入: nums = [1, 3, 2, 2, 3, 1] 输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]说明: 你可以假设所有输入都会得到有效的结果。
进阶: 你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
先对数组排序，分为大数部分和小数部分，再穿插排序。 注意顺序，例如[1，2，4，4，4，6]这个数组，通过降序穿插得到[4,6,2,4,1,4]。 如果顺序排列，则会得到[1,4,2,4,4,6]不满足要求。
复杂度分析 时间复杂度O（nlogn） 空间复杂度O（n）
class Solution { public: // 排序后穿插赋值 // 时间复杂度O(nlogn)，空间复杂度O(n) void wiggleSort(vector<int>& nums) { if(nums.size() <= 1) return; sort(nums.begin(),nums.end()); vector<int> a(nums); int n = a.size(); int j = (n+1)/2 -1, k = n-1; int jj = j; for (int i = 0; i<n;){ if (j> -1) nums[i++] = a[j--]; if(k > jj) nums[i++] = a[k--]; } } };三向切分 （1）寻找第 k 大的元素，这里选择第 n/2 大元素，即寻找中位数，假设它的值是 mid，可以使用 O(n) 搞定它。因为 cpp 库已经提供了 nth_element 这个函数了，就不重复造轮子了，感兴趣的同学，参考 215 题：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/comments/64977 （2）三向切分，整个数组被切分成 [------,======,+++++]，即荷兰国旗问题，参考 75 题：https://leetcode-cn.com/problems/sort-colors/comments/64938 。三向切分注意，我们需要把比 mid 大的数安排到 mid 左边，比 mid 小的数安排到 mid 右边，最后数组大概像是这样 [++++++,=====,-------]. 当你掌握了上面两个基础技术后（强烈建议去做一下 75、215)。
怎么把一个三向切分好的数组变成摆数组，可以使用“索引”映射这个方法（有人称为索引改写，有人称为虚拟索引，怎么说都行，我也是从大神那里学习过来的），假设数组大小是 6
0 1 2 3 4 5 [1 1 1 3 4 5] [3 1 4 1 5 1]0->1 1->3 2->5 3->0 4->2 5->4 意思是说，做映射后，把位置 0 的元素安排到位置 1 上，把位置 1 安排到位置 3 上，位置 2 安排到位置 5 上，位置 3 安排到位置 0 上，位置 4 安排到位置 2 上，而位置 5 安排到位置 4 上。这样安排后，数组就变以了摆动数组。
实际上，我们可以把三向切分的过程，和数组索引映射合并到一起完成。在程序里，我们定义映射后的数组为 a(i) = nums[2*i+1] % (n|1)，在三向切分的时候，对 a(i) 进行操作即可。 (n|1) 的含义：不小于n的最小奇数
该题的重点在找到映射关系a(i) = nums[2*i+1] % (n|1)。与荷兰国旗问题思路相同，都是通过一次遍历，交换值得到序列。不同的是荷兰国旗问题是将未排序的序列排序，该题是将排序号的序列变为摆动排序。
复杂度分析 时间复杂度O（n） 空间复杂度O（1）
class Solution { public: void wiggleSort(vector<int>& nums) { int n = nums.size(); std::nth_element(nums.begin(), nums.begin() + n/2, nums.end()); int mid = nums[n/2]; // 3-way-partion int i = 0; int j = 0; int k = n - 1; #define a(i) nums[(2*(i)+1)%(n|1)] while (j <= k) { if (a(j) > mid) { swap(a(i), a(j)); ++i; ++j; } else if (a(j) < mid) { swap(a(j), a(k)); --k; } else { ++j; } } } };