在一个给定的乱序的序列中找到第k个数字，可能会想到先排序，然后输出第k个数。这种方法简单粗暴，时间复杂度为O(nlogn)。

　　还有一种方法是快速选择，它的思想和快速排序很相似。就是先选择一个数x，然后把这个序列分成左右两边，其中左边的所有的数都<=x，右边的数都>=x。然后比较左边数字的个数leftNum与k的大小。如果k <= leftNum，说明我们要找到第k个数在调整后的序列的左边那部分；否则就是在右边的那部分。然后再用相同的方法递归那部分来找到第k个数。

　　我们在这个序列中随便找到一个数x，接下来和快速排序一样，把这个序列调整为左边的部分的数都<=x，右边部分的数都>=x。

　　其中指针j就为划分左右两边的下标位置，j的左边（包括j这个位置）就是左部分，右边就是右部分。

　　接下来计算左边部分元素的个数leftNum = j - left + 1，与k进行比较：

• 如果k <= leftNum，说明我们要找的第k个数就在左边部分，递归去在左边部分找第k个数，寻找序列的下标范围是[left, j]；
• 否则如果k > leftNum，说明我们要找的第k个数在右边部分，这时应该是递归去在右边部分找第k - leftNum个数，相应的寻找序列的下标范围应该为[j + 1, right]。

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

　　可以试想假设序列有n个元素，开始的第一次寻找次数为n，然后把序列分成左右两部分，有相关证明两边的期望大小各为为n/2，我们要在其中的一部分找。然后同样的方法又分成两部分，为n/4。以此类推，所以有

\[n + \frac{n}{2} + \frac{n}{4} + ... = n (1 + \frac{1}{2} + \frac{1}{4} + ...) = n\lim_{m->\infty }\sum_{i = 1}^{m} \frac{1}{2^{i}} = 2n\]

　　所以时间复杂度就为O(n)了。

　　相应的代码就通过一道模板题来给出吧。

786. 第k个数

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在 1∼10⁹ 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 k 小数。

数据范围

1≤n≤100000,
1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

 　　AC代码如下：

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int solve(int *a, int left, int right, int k) {
 6     if (left == right) return a[left];      // left == right，说明只有一个数字，这个数字就是我们要找到的第k个数
 7     int x = a[left + right >> 1], i = left - 1, j = right + 1;
 8     while (i < j) {
 9         while (a[++i] < x);
10         while (a[--j] > x);
11         if (i < j) swap(a[i], a[j]);
12     }
13     
14     int leftNum = j - left + 1;
15     if (k <= leftNum) return solve(a, left, j, k);
16     else return solve(a, j + 1, right, k - leftNum);
17 }
18 
19 int main() {
20     int n, k;
21     scanf("%d %d", &n, &k);
22     int a[n];
23     for (int i = 0; i < n; i++) {
24         scanf("%d", a + i);
25     }
26     printf("%d", solve(a, 0, n - 1, k));
27     
28     return 0;
29 }

参考资料

　　AcWing 786. 第k个数：https://www.acwing.com/video/228/