摆动排序II

变量简洁正确完整思路
快速选择找到中点n-1)/2的值midNum
找到中点midNum后，用三分法将<放左边，=放中间，>放右边，
00 111 56   i从mid往左，j从n-1往左，才能1这个重复的放在最两侧
不能i从0往右，j从mid+1往右，不能保障1这个重复的在最左边
三分法123222225走一遍，可以给一个num，分成<  =  >三部分，i前面是<，k后面是>，ij从0开始，k从n-1开始
numj大于num就把numj放到numk处k--但j不能++因为k的数可能是<的，numj小于num就把numj放到numi处并
i++j++，为什么用j++因为i的一定是小于或者等于的，否则j++

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n=nums.size();
        //快速选择
        int mid=(n-1)/2;
        dfs(0,n-1,mid,nums);
        //三分法
        int midNum=nums[mid];
        threePart(nums,midNum);
        int i=mid,j=n-1;
        vector<int>tmp;
        while(i>=0){
            tmp.push_back(nums[i]);i--;
            if(j>mid){
                tmp.push_back(nums[j]);j--;
            }
        }
        copy(tmp.begin(),tmp.end(),nums.begin());
    }
    void threePart(vector<int>&nums,int midNum){
        int i=0,j=0,k=nums.size()-1;
        while(j<k){
            if(nums[j]>midNum){
                swap(nums[j],nums[k]);
                k--;
            }else if(nums[j]<midNum){
                swap(nums[j],nums[i]);
                i++,j++;
            }else j++;
        }
    }
    void dfs(int beg,int end,int mid,vector<int>&nums){
        if(beg>end)return;
        int i=beg,j=end;
        while(i<j){
            while(nums[j]>=nums[beg]&&j>i)j--;
            while(nums[i]<=nums[beg]&&i<j)i++;
            if(i<j)swap(nums[i],nums[j]);
        }
        swap(nums[beg],nums[i]);
        if(i==mid)return;
        if(i<mid)dfs(i+1,end,mid,nums);
        if(i>mid)dfs(beg,i-1,mid,nums);
    }
};