摆动排序

把数组排成“小-大-小-大”的样子。

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]...

https://leetcode.com/problems/wiggle-sort-ii

按逆序按中位数划分两半；把[N/2..]（后面小的一半或一半多1）放在偶位，再把[0..N/2)（前面大的一半）放在奇位。

比如 1 2 3 3 3 3 4 5，逆序 5 4 3 3 3 3 2 1
先把 3 3 2 1 逆序放在偶位：3 · 3 · 2 · 1
再把 5 4 3 3 逆序放在奇位：· 5 · 4 · 3 · 3
变成：3 5 3 4 2 3 1 3

这种把后一半坐标[N/2..]放到偶位、[0..N/2)放到奇位的下标映射是：idx => (idx*2+1)%(N|1)

比如 0 1 2 3 4 5 6 7
逆序 7 6 5 4 3 2 1 0
变成 3 7 2 6 1 5 0 4
下标 6 4 2 0 7 5 3 1

若把数组排成“大-小-大-小”的样子。

按中位数划分两半；把[N/2..]（后面大的一半或一半多1）放在偶位，再把[0..N/2)（前面小的一半）放在奇位。
比如 1 2 3 3 3 3 4 5
先把 3 3 4 5 放在偶位：3 · 3 · 4 · 5
再把 1 2 3 3 放在奇位：· 1 · 2 · 3 · 3
变成：3 1 3 2 4 3 5 3

可以把按中位数划分、按奇偶位摆放两个过程整合，在“三路划分”的过程中用虚拟索引摆放到位，这样只要O(1)空间。

void wiggleSort(vector<int>& nums) {
    const int N = nums.size();
    // 按逆序处理，下面先找media、再按>median三路划分
    // 可自己实现findKthLargest，其中k是1-based，中位数k=(N+1)/2
    // int median = findKthLargest(nums, (N + 1) / 2);
    // 见 https://leetcode.com/problems/kth-largest-element-in-an-array/
    // 这里也可以调用nth_element(..., greater<int>())，其中midptr是0-based
    auto midptr = nums.begin() + (N - 1) / 2; // 0-based偏移中位数(N+1)/2-1
    nth_element(nums.begin(), midptr, nums.end(), greater<int>());
    int median = *midptr;
    
    // 把后一半坐标[N/2..]放到偶位、前一半坐标[0..N/2)放到奇位的下标映射：i => (2*i+1) % (N|1)
    // 见 https://leetcode.com/problems/wiggle-sort-ii/discuss/77677/O(n)+O(1)-after-median-Virtual-Indexing
    auto idx = [&](int i) { return (2*i+1) % (N|1); };
    // 三路划分：| >median | =median |  ?  | <median |
    //          0         i         j    k        N-1
    // i指向>median待写入位置，j指向待处理位置，k指向<median待写入位置
    int i = 0, j = 0, k = N - 1;
    while (j <= k) {
        if (nums[idx(j)] > median) {
            swap(nums[idx(j)], nums[idx(i)]);
            i++, j++;
        } else if (nums[idx(j)] < median) {
            swap(nums[idx(j)], nums[idx(k)]);
            k--;
        } else {
            j++;
        }
    }
}

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

https://leetcode.com/problems/wiggle-sort/

条件更宽松，<=、>=，只要把不符合要求的相邻数对换

void wiggleSort(vector<int>& nums) {
    for (int i = 0; i + 1 < nums.size(); i++) {
        if ((i % 2 == 0 && nums[i] > nums[i+1]) || (i % 2 == 1 && nums[i] < nums[i+1])) {
            swap(nums[i], nums[i+1]);
        }
    }
}

最长摆动子序列、最长摆动子段只需用贪心法