• 注意：整数二分 和 快排快选 的 边界情况 非常多，建议 理解之后 背个模板 就ok了，y总 说 不背模板第一次写对的概率 跟中彩票一样多 hh。

• 快选 和 快排 的区别：

• 大雪菜模板

1. 快速排序（分治）：时间O(nlogn)

• 题目：AcWing 785. 快速排序
• 优质题解：高赞 醉生梦死：快速排序算法的证明与边界分析

1.1 时间复杂度：O(nlogn)

• 时间复杂度：内部调整时间([l, r] 分成 <= x 和 >= x 两段) 是 O(n)，每次除以2，期望是会递归 logn 层，所以 总的 平均时间复杂度 是 O(nlogn)，最坏情况下是 O(n^2)的。

• 难点是 第 2 步，如何优雅的 把区间划分为 >= x 和 <= x 的两段（注意 区间 分界点 处的数 不一定 等于 x）。

• 把 q 数组 区间划分为 >= x 和 <= x 的两段，不优雅的做法：暴力法，额外开 两个数组 a 和 b，然后 遍历一遍，在遍历过程中 将 <= x 的数 加入数组 a，将 >= x 的数 加入 数组 b。最后 再遍历 a 和 b 一遍，依次把 数组 a 和 数组 b 中的数 放进 数组 q。这样虽然遍历 两遍，不过 时间复杂度倒还是 O(n)，但是 因为开了两个额外数组，空间复杂度 就变为 O(n) 了。

• 优雅的做法 就是采用双指针，具体做法见 代码 。要注意的是 虽然 区间分为 >= x 和 <= x 的两段，但是 代码中 while (q[i] < x) 和 while (q[j] > x) 均不带 '='。

• i,j 两指针相遇后，只有两种情况，(1) i == j; (2) i > j。如 图中 例1 例2所示：

1.2 代码

void quick_sort(int q[], int l, int r) {
    // 当数组为空时，quick_sort( q, 0, len(q) - 1 )中l = 0, r = -1, 会出现 l > r的情况
    // 除了 一开始 需要判断 l > r, 以后 只需要 判断 l == r 即可
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) // i,j 两指针相遇后，只有两种情况，(1) i == j; (2) i > j
    {
        do i ++ ; while (q[i] < x); // 注意 不是 " <= ", 没有 等号
        do j -- ; while (q[j] > x); // 注意 不是 " >= ", 没有 等号
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

• 注意if (l >= r) return; 中一定是 >=，不能只用 "=="，因为一开始假如数组为空，r = length(q) - 1 = -1，此时 l = 0, l > r。

2. 快速选择 ：时间O(n)

• 题目：lc 215. 数组中第K大的数.md，AcWing 786. 第k个数

2.1 时间复杂度：O(n)

• 第一次，内部调整时间([l, r] 分成 <= x 和 >= x 两段) 是 O(n)。
• 每次除以2，期望递归 n + n/2 + n/4 + ...，以n为首项，1/2为等比数列q的等比数列的和） = O(n)，所以 总的 平均时间复杂度 是 O(n)，最坏情况下是 O(n^2)的。

• 快选 和 快排 的区别：

2.2 y总 快选 代码：时间 O(n), 空间 O(logn)

• 相关题目：AcWing 786. 第k个数
• 可以把 递归栈空间 去掉，进行空间优化，如2.3 中所示

// 时间 O(n), 空间 O(logn)
#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

int quick_select(int q[], int l, int r, int k) {
    // 当数组为空时，quick_sort(q, 0, len(q) - 1)中l = 0, r = -1, 会出现 l > r的情况
    // 除了 一开始 需要判断 l > r, 以后 只需要 判断 l == r 即可
    // 因为 快速选择 传进来的 序列 最少有一个元素, 所以 一般 len(q) >= 1, 不用判断 l > r 也可以
    // 除了 len(q) == 0 会造成 一开始 l > r 之外，以后return 的时候 肯定有 l == r
    if (l >= r) return q[l];

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) // i,j 两指针相遇后，只有两种情况，(1) i == j; (2) i > j
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    if (j - l + 1 >= k) return quick_select(q, l, j, k);
    else return quick_select(q, j + 1, r, k - (j - l + 1));
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    cout << quick_select(q, 0, n - 1, k) << endl;

    return 0;
}

• 和快速排序不同，if (l >= r) return q[l];中 >=可以写成==，因为求 第 k 小 的数，一般 传进来的数组 不为空

2.3 y总 快选 代码 空间优化： 空间 O(logn) 优化到O(1)

• 相关题目：lc 215. 数组中第K大的数
• y总快选 优化空间，去掉递归栈空间，直接用while循环. 时间O(n)， 空间O(1)

2.3.1 y总 快选 代码 有递归栈空间. 时间O(n)，空间O(logn)

// 时间复杂度：O(n), 空间复杂度: 递归栈空间O(logn)
// y总 代码 没有 随机选取 x , 导致 用时比较长 44ms. 随机后 4ms
// 如果 x 每次都选 nums[l] 或 nums[r], 碰到 升序或降序的 极端样例, 时间O(n^2),, 用时会很久
// 而且 nums[l] 和 nums[r] 的代码边界不一样, 容易出错, 建议选 nums[l + r >> 1]
// 选取 nums[l] 的 用时 在 40ms 左右, 选取 nums[r]需要修改一下边界情况, 没有改, 应该也40ms左右
// 选取 nums[l + r >> 1] 跟 随机选取 nums[rand() % (r - l + 1) + l] 时间差不多, 在 4ms 左右
class Solution {
public:

    int quick_select(vector<int>& nums, int l, int r, int k) {
        if (l >= r) return nums[l];
        // int i = l - 1, j = r + 1, x = nums[l + r >> 1]; // 选取 nums[l], 极端样例 时间会很久
        int x = nums[rand() % (r - l + 1) + l], 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(nums[i], nums[j]);
        }
        if (k <= j - l + 1) return quick_select(nums, l, j, k);
        else return quick_select(nums, j + 1, r, k - (j - l + 1));
    }

    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0)); // 随机种子
        return quick_select(nums, 0, nums.size() - 1, k);
    }
};

2.3.2 y总快选 优化空间，去掉递归，直接用while循环. 时间O(n)， 空间O(1)

// 时间复杂度：O(n), 空间复杂度: O(1)
// y总 代码 去掉递归, 用 while 循环, 就不用 递归栈空间 了.
// 原来的 递归 只是 相同的代码, 只不过 递归时 递归的参数 区间端点值 l,r 以及 k变了
// 这里 while 每次循环 也是 用 相同的代码, 只不过 是 每次循环之后 将 l,r 以及 k 更新
class Solution {
public:
     int quick_select(vector<int>& nums, int l, int r, int k) {
         while(true) {
             if (l == r) return nums[l];
             int i = l - 1, j = r + 1, x = nums[l + r >> 1]; // 选取 nums[l], 极端样例 时间会很久
             // int x = nums[rand() % (r - l + 1) + l], 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(nums[i], nums[j]);
             }

             // 将 递归 的 参数l,r,k变化 改为 while 循环中 l,r,k 更新, 省去递归栈空间
             // if (k <= j - l + 1) return quick_select(nums, l, j, k);
             if (k <= j - l + 1) r = j;
             // else return quick_select(nums, j + 1, r, k - (j - l + 1));
             else k = k - (j - l + 1), l = j + 1; // 注意 k更新用到 l, 所以 l 更新应该在 k更新之后
         }
     }

     int findKthLargest(vector<int>& nums, int k) {
         srand(time(0)); // 随机种子
         return quick_select(nums, 0, nums.size() - 1, k);
     }
};