lc324. 摆动排序 II（快速选择 三数排序）

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

你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
示例 2：

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

提示：

1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

class Solution {
    /**
    快速选择On找出中位数，然后利用三数排序On将数组排序成三部分，再穿插
     */
    int[] nums;
    int n;
    int qselect(int l, int r, int k) {
        if (l == r) return nums[l];
        int x = nums[l + r >> 1];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do ++i; while (nums[i] < x);
            do --j; while (nums[j] > x);
            if (i < j) swap(i, j);
        }
        int cnt = j - l + 1;
        if (k <= cnt) return qselect(l, j, k);
        else return qselect(j + 1, r, k - cnt); 
    }
    void swap(int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
    public void wiggleSort(int[] nums) {
        this.nums = nums;
        n = nums.length;
        // 快速选择找中位数
        int mid = qselect(0, n - 1, n + 1 >> 1);
        // 让数组变为三段
        int l = 0, r = n - 1, loc = 0;
        while (loc <= r) {
            if (nums[loc] < mid) swap(loc ++, l ++);
            else if (nums[loc] > mid) swap(loc, r--);
            else loc ++;
        }
        int[] clone = nums.clone();
        int idx = 1; loc = n - 1;
        while (idx < n) {
            nums[idx] = clone[loc--];
            idx += 2;
        }
        idx = 0;
        while (idx < n) {
            nums[idx] = clone[loc--];
            idx += 2;
        }
    }
}