快速排序之第k个数

找到第k个小的数。使用快速选择算法

时间复杂度比快速排序低。因为题目不要求排序只需要选择。每次快速排序之后分成左右两边，这个时候我们就看第k个数在哪里。

如果k在左边，那就是左边的第k个数；如果k在右边，那就是右边的第 length(left) - k个数

快速选择算法的时间复杂度是 O(n)

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];

int quick_sort(int l, int r, int k) {
    if (l == r ) return a[l];
    int x = a[(l + r) >> 1];
    int i = l - 1, j = r + 1;
    while (i < j ) { // 跳出循环的时候有两种情况一种是i和j重合，另一种是i = j + 1
        while (a[++ i ] < x ) ;
        while (a[-- j ] > x ) ;
        if (i < j) swap(a[i], a[j]);
    }
    int sl = j - l + 1;
    if (k <= sl ) return quick_sort(l, j, k);
    // 在左边的话就直接返回
    // 在右边的话就减少一个区间
    else return quick_sort(j + 1, r, k - sl);
}


int main () {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    printf("%d\n", quick_sort(0, n - 1, k));
    return 0;

}

这里写 while (a[++ i ] < x ) ;是因为有的语言没有 do while();写法所以这样写。意思是先给 i做一个自增，然后判断 a[i]和 x的大小关系。所以会出现 i在 j后面一个的情况。