leetcode324 摆动排序II

 　　1. 首先考虑排序后交替插入

　　首尾交替插入，这种方法对于有重复数字的数组不可行；

class Solution {

public:

    void wiggleSort(vector<int>& nums) {

        //因为一定存在最优解，所以一定可行的方法就是先排序，然后将最小的数逐渐插入到最大里面；

        //错误，没有考虑重复答案存在情况；

        sort(nums.begin(),nums.end());

        int i=;

        int j=nums.size()-;

        vector<int> res;

        while(i<=j){

            if(i<=j)

                res.push_back(nums[i++]);

            if(i<=j)

                res.push_back(nums[j--]);

        }

        for(int i=;i<nums.size();i++){

            nums[i]=res[i];

        }

    }

};

对此进行改进：

class Solution {

public:

    void wiggleSort(vector<int>& nums) {

        //因为一定存在最优解，所以一定可行的方法就是先排序，然后将最小的数逐渐插入到最大里面；

        //改进，将前后两个数组反序如1 2 3 4 5 6 分为 【3 2 1】，【6 5 4】然后按顺序插入；

        sort(nums.begin(),nums.end());

        vector<int> res;

        int mid=(nums.size()+)/;

        int i=mid-;int j=nums.size()-;

        while(i>=){

            if(i>=) res.push_back(nums[i--]);

            if(j>=mid) res.push_back(nums[j--]);

        }

        for(int i=;i<nums.size();i++){

            nums[i]=res[i];

        }

    }

};

采用快排：

class Solution {

public:

    int partition(vector<int>& nums,int l,int r){

        int pivot=nums[l];

        while(l<r){

            while(l<r && nums[r]>=pivot)

                r--;

            nums[l]=nums[r];

            while(l<r && nums[l]<=pivot)

                l++;

            nums[r]=nums[l];

        }

        nums[l]=pivot;

        return l;

    }

    void quicksort(vector<int>& nums,int start,int end){

        if(start>=end) return;

        int pivot=partition(nums,start,end);

        quicksort(nums,start,pivot-);

        quicksort(nums,pivot+,end);

    }

    void wiggleSort(vector<int>& nums) {

        //因为一定存在最优解，所以一定可行的方法就是先排序，然后将最小的数逐渐插入到最大里面；

        quicksort(nums,,nums.size()-);

        vector<int> res;

        int mid=(nums.size()+)/;

        int i=mid-;int j=nums.size()-;

        while(i>=){

            if(i>=) res.push_back(nums[i--]);

            if(j>=mid) res.push_back(nums[j--]);

        }

        for(int i=;i<nums.size();i++){

            nums[i]=res[i];

        }

    }

};

以上方法的时间复杂度为O(nlogn) 空间复杂度为O(n)

　　2. 还有时间复杂度为O(n)的原地方法：

空间复杂度为O(1),

leetcode324 摆动排序II的相关教程结束。