# LeetCode Wiggle Sort II

LeetCode Wiggle Sort II

Given an unsorted array `nums`, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`.

Example:
(1) Given `nums = [1, 5, 1, 1, 6, 4]`, one possible answer is `[1, 4, 1, 5, 1, 6]`.
(2) Given `nums = [1, 3, 2, 2, 3, 1]`, one possible answer is `[2, 3, 1, 3, 1, 2]`.

Note:
You may assume all input has valid answer.

Can you do it in O(n) time and/or in-place with O(1) extra space?

```class Solution {
private:
//自己实现的快排程序
void my_quick_sort(vector<int>& nums, int s, int t) {
int i = s, j = t, pivot = s;
if (i >= j)return;
while (i <= j) {
while (i <= j&&nums[i] <= nums[pivot])++i;
if (i > j)break;
while (i <= j&&nums[j] >= nums[pivot])--j;
if (i > j)break;
swap(nums[i++], nums[j--]);
}
swap(nums[pivot], nums[j]);
my_quick_sort(nums, s, j - 1);
my_quick_sort(nums, j + 1, t);
}
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
my_quick_sort(nums, 0, n - 1);
int i = (n & 1) == 0 ? n / 2 - 1 : n / 2, j = n - 1;
vector<int> ans(n, 0);
for (int k = 0; k < n; ++k) {
ans[k] = (k & 1) == 0 ? nums[i--] : nums[j--];
}
nums = ans;
}
};
```

```class Solution {
public:
void wiggleSort(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), i = (n + 1) / 2, j = n;
vector<int> ans(n, 0);
for (int k = 0; k < n; ++k) {
ans[k] = (k & 1) == 0 ? nums[--i] : nums[--j];
}
nums = ans;
}
};
```