01_快速排序 quick_sort

递归:

1）终止条件
2）本级递归（通用）需要做什么
3）返回值

注: 不要纠结每一级的细节，认真就输了

选择排序是从全局到局部，递归语句放在最后
归并排序是从局部到全局，递归语句放在前面

#include <iostream>

using namespace std;

const int N = 100010;
int n, a[N];

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;

    /*
    基准值 x 的选择: （为什么以 i, j 划分是这两个区间: 理由看函数最下面递归区间的选择）
        1) 以 j 为划分 -> (l ~ j) & (j + 1 ~ r): 
            x 不能取到右边界 a[r]！！！(若取中点要向下取整，否则可能取到 a[r])，
            否则此时某些情况下 j 会取到 r，quick_sort(a, l, j) 会造成规模无法缩小，会无限划分，
            例: 若 x 取 a[r]，且 a[l ~ r - 1] < a[r] (ooooO)
                则一轮循环结束时 i = r, j = r -> quick_sort(a, l, j) 无限划分，死循环 q(l, r)
                若 x 取 a[l]，两区间都不会无限划分，可行

        2) 以 i 为划分 -> (l ~ i - 1) & (i ~ r): 
            x 不能取到左边界 a[l]！！！(若取中点要向上取整，否则可能取到 a[l])，
            否则此时某些情况下 i 会取到 l，quick_sort(a, i, r) 会造成规模无法缩小，会无限划分，
            例: 若 x 取 a[l]，且 a[l] < a[l + 1 ~ r] (oOOOO)
                则一轮循环结束时 i = l, j = l -> quick_sort(a, i, r) 无限划分，死循环 q(l, r)
                若 x 取 a[r]，两区间都不会无限划分，可行
    */
    int x = a[l + r >> 1];

    int i = l - 1, j = r + 1; // 为了用 do-while，理由看下面

    /*
    为什么外层 while 的判断条件不能取 i <= j: 
        若 while (i <= j)，则 j 在某些情况会取到 l - 1，此时会发生无限划分
        例: 若只有两个元素 {a, b}，且 a < b，
            则一轮循环 i = l, j = l（正常到这应该跳出循环），
              二轮循环 i = r, j = l - 1，此时会造成 quick_sort(a, j + 1, r) 的无限划分
    */
    while (i < j) {
        /* 
        为什么用 do-while: 
            若用 while，当 a[i] 和 a[j] 都为 x 时, i 和 j 都不会更新，导致死循环，
            所以用 do-while，保证每次循环 i 和 j 都能移动 
        */
        /* 
        为什么内层 while 的判断条件不能用 <= : 
            例: 若元素全相等，则 i 或 j 会造成数组下标超界
        */
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    /* 
    递归区间的选择: 
        跳出 i < j 的 while 循环时: i >= j（ij不是重合就是紧挨着: l...i(j)...r 或 l...ji...r）
        可以确定的是: 
            a[l ~ j] <= x
            a[l ~ i - 1] <= x
            a[i ~ r] >= x
            a[j + 1 ~ r] >= x
        此时可选区间: (l, j)&(i, r), (l, i - 1)&(j + 1, r), (l, j)&(j + 1, r), (l, i - 1)&(i, r)
        又因为 (l, i - 1)&(j + 1, r) 可能会出现区间遗漏，
               (l, j)&(i, r) 可能会出现区间重叠（重复处理导致规模无法缩小，会无限递归，
                                                例: {1, 2} => q(0, 1) => q(0, 0)&q(0, 1) => …）
        所以最后可选区间: (l, j)&(j + 1, r), (l, i - 1)&(i, r)
        注意: 若以 i 划分: quick_sort(a, l, i - 1), quick_sort(a, i, r);
              则只需让 x 向上取整: a[l + r + 1 >> 1]，理由看函数最上面 x 取值的选择
    */
    quick_sort(a, l, j), quick_sort(a, j + 1, r); // 以 j 划分
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    quick_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";

    return 0;
}

02_第 k 个数 kth_number

(1)

#include <iostream>

using namespace std;

const int N = 100010;
int n, a[N], k;

int quick_select(int a[], int l, int r) {
    if (l >= r) return a[l];

    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    if (k - 1 <= j) return quick_select(a, l, j);   // 递归左半边
    return quick_select(a, j + 1, r);               // 递归右半边
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << quick_select(a, 0, n - 1) << endl;

    return 0;
}

(2)

#include <iostream>

using namespace std;

const int N = 100010;
int n, a[N], k;

int quick_select(int a[], int l, int r, int k) {
    if (l >= r) return a[r];

    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    int sl = j - l + 1; // sl 是左半边的长度
    if (k <= sl) return quick_select(a, l, j, k);
    /*
    k - sl: 在当前区间是第 k - sl 个
    相当于砍绳子，在局部查找
    此时序号 k 不基于 a 而是基于 a 的某个区间，所以最后返回的是 a[l] 或 a[r]
    */
    return quick_select(a, j + 1, r, k - sl);
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << quick_select(a, 0, n - 1, k);

    return 0;
}