要求：小大小大…。时间O(n)或者空间O(1)
思路：
法一：桶代替排序
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int bucket[5001]={0};
for(int num:nums)bucket[num]++;
int len=nums.size();
int small,big;//穿插数字时的上界
//总长度为奇数时，“小 大 小 大 小”边界左右都为较小的数；
//总长度为偶数时，“小 大 小 大”边界左为较小的数，边界右为较大的数
if((len&1)==1){
small=len-1;
big=len-2;
}else{
small=len-2;
big=len-1;
}
int j=5000; //从后往前，将桶中数字穿插到数组中，后界为j
//桶中大的数字在后面，小的数字在前面，所以先取出较大的数字，再取出较小的数字
//先将桶中的较大的数字穿插放在nums中
for(int i=1;i<=big;i+=2){
while (bucket[j]==0)j--;//找到不为0的桶
nums[i]=j;
bucket[j]--;
}
//再将桶中的较小的数字穿插放在nums中
for(int i=0;i<=small;i+=2){
while (bucket[j]==0)j--;//找到不为0的桶
nums[i]=j;
bucket[j]--;
}
}
};
法二：先快排找中间的数，然后跟中间的数相同的聚拢到中间，这样数组分为三部分，然后按中间右边的顺序写回开头
class Solution {
private:
int p,size;
public:
//find the (size+1)/2th num
void quick_pick(vector<int>& nums,int left,int right){
int l=left,r=right;
while(left<right){
while(left<right&&nums[right]>=nums[left])right--;
swap(nums[left],nums[right]);
while(left<right&&nums[left]<=nums[right])left++;
swap(nums[left],nums[right]);
}
if(left==p)return;
else if(left>p)quick_pick(nums,l,left-1);
else quick_pick(nums,left+1,r);
}
void wiggleSort(vector<int>& nums) {
size=nums.size();
if(size<2)return;
p=(nums.size()+1)/2;
vector<int> helper=nums;
quick_pick(helper,0,size-1);
int left=p-1,right=p+1;
//put the mid num together
for(int i=p-1;i>=0;i--){
if(helper[i]==helper[p]){
swap(helper[i],helper[left]);
left--;
}
}
for(int i=p+1;i<size;i++){
if(helper[i]==helper[p]){
swap(helper[i],helper[right]);
right++;
}
}
//write the result back
int l=p-1,r=size-1,i=0;
while(i<size){
nums[i++]=helper[l--];
if(i<size)nums[i++]=helper[r--];
}
}
};
