题目描述

给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

示例 1:

输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]

思路：

可以将数组切分为两部分 一部分的所有数小于另一部分中的所有数。
方法是首先求出数组的中值，接着按照荷兰旗的思路将数组分为大于，小于，等于中值的三个部分
最后将两部分数组交叉，注意对奇偶数据的处理

C++ 代码

#include<vector>

using namespace std;


class Solution {
public:

    int partition(vector<int>& nums, int start, int end) {
        int i = start, j = start;
        while(i<end){
            if (nums[i] < nums[end]) {
                swap(nums[i], nums[j++]);
            }
            i++;
        }
        swap(nums[j], nums[end]);
        return j;
    }
    int k;
    void quick_select(vector<int>& nums, int start,int end) {
        if (start > end)return;
        int par = partition(nums,start,end);
        if (par == k)return;
        else if(par<k){
            quick_select(nums, par + 1, end);
        }
        else quick_select(nums, start, par - 1);
    }

    void wiggleSort(vector<int>& nums) {
        //区分为两块，使得左块的元素均小于右边的元素
        k = nums.size() >> 1-1;
        quick_select(nums,0,nums.size()-1);
        int mid_val = nums[k];
        int left = 0,cur = 0, right = nums.size() - 1;
        while (cur < right) {
            if (nums[cur] < mid_val) {
                swap(nums[cur], nums[left]);
                cur++;
                left++;//left指向小于元素的最后一位
            }
            else if (nums[cur] > mid_val) {
                swap(nums[cur], nums[right--]);
            }
            else {
                cur++;
            }
        }

        vector<int> res(nums);
        for (int i = 0; i <= k; i++) {
            nums[2 * i] = res[k - i];
            nums[2 * i + 1] = res[nums.size() - 1 - i];//3 
        }
        if (nums.size() & 1)nums[nums.size() - 1] = res[0];
    }
};