Three-way Partition

问题来源于the Dutch national flag problem，荷兰国旗问题？

把数组重新排序，比mid小的在前面，等于mid的在中间，比mid大的在最后，类似于快速排序中的partition

循环里，i <= j 保持不变，n是比mid大的数字在数组中的索引下界，j是当前考虑的数字的索引，i是比mid小的数字在数组中的索引上界，只有当遇到mid时j才会大于i

void partition(vector<int>& arr, int mid){
    int i = 0, j = 0, n = arr.size() - 1;
    while(j <= n){
        if(arr[j] < mid)
            swap(arr[i++], arr[j++]);
        else if(arr[j] > mid)
            swap(arr[j], arr[n--]);
        else
            j = j + 1;
    }
}

时间复杂度为O(n)

空间复杂度O(1)

LeetCode 326 Wiggle Sort II

Give an unsorted array nums, reorder it such that $nums[0] < nums[1] > nums[2] < nums[3]....$, assume all input has valid answer.

O(n) time O(1) extra space

void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    
    // Find a median.
    auto midptr = nums.begin() + n / 2;
    nth_element(nums.begin(), midptr, nums.end());
    int mid = *midptr;
    
    // Index-rewiring.
    #define A(i) nums[(1+2*(i)) % (n|1)]

    // 3-way-partition-to-wiggly in O(n) time with O(1) space.
    int i = 0, j = 0, k = n - 1;
    while (j <= k) {
        if (A(j) > mid)
            swap(A(i++), A(j++));
        else if (A(j) < mid)
            swap(A(j), A(k--));
        else
            j++;
    }
}

Virtual indexing: map of subscript, from 0~mid to odd numbrs(1, 3, 5, 7...), and from mid + 1~n - 1 to even  numbers(0, 2, 4, 6...). So the big numbers which formerly in 0~mid will be placed in 1, 3, 5, 7..., and small numbers in 0, 2, 4, 6...