Problem：

给你N个数字，大小都不相同，没有顺序，如何找到其中第K大的数？

Solution1 排序:

最直接的想法，排序，然后选第k个即可。时间复杂度O(NlogN) 优点，代码简单。缺点：比较慢

#include <cstdio> #include <algorithm> using namespace std; int a[1000005]; bool comp(const int &a, const int &b) { return a > b; } int main(int argc, char *argv[]) { int n, k; while(scanf("%d%d", &n, &k) != EOF) { for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } sort(a, a + n, comp); printf("%d\n", a[k - 1]); } return 0; }

Solution2: 巧妙使用快排框架

回想快排的特点，每次取轴之后可以保证左侧比轴小，右侧比轴大。这样的话每次找到轴的位置，如果小于K，说明K在右侧，只排右侧，反之，只排左侧。 时间复杂度平均O(n)，但是最坏复杂度是O(n²)，因为轴的位置不一定能把两个子问题划分的均等。

#include <cstdio> #include <random> using namespace std; int a[1000005]; int findK_by_quick(int begin, int end, int k) { if (begin == end) return a[begin]; int mid = (begin + end) >> 1; int choice = begin + random() % (end - begin + 1); int r = a[choice]; a[choice] = a[begin]; a[begin] = r; int i = begin, j = end; while(i < j) { while(a[j] <= r && i < j) { j--; } while(a[i] >= r && i < j) { i++; } int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } a[begin] = a[i]; a[i] = r; if (i == k) { return a[i]; } else if (i > k){ return findK_by_quick(begin, i - 1, k); } else { return findK_by_quick(i + 1, end, k); } } int main(int argc, char *argv[]) { int n, k; while(scanf("%d%d", &n, &k) != EOF) { for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } printf("%d\n", findK_by_quick(0, n - 1, k - 1)); } return 0; }

Solution3: 大牛中位数算法BFPTR

这个算法发明的人简直是大神，但是虽然具有理论上的O(n)复杂度，不过因为常数项太大一般实际效果不一定好。这个算法的推导和具体的实现算法课PPT上有，不再赘述。。。也不想再推一遍了。。。 基本思想是：前面快排通过随机取轴只能保证期望最优，但是如果有方法始终保证轴是中位数，就一定可以保证最优。 那么问题就变成了如何较快的寻找一组数字的中位数，这个算法每5个一组排序，然后找到每个组中位数，再对这些中位数每5个一组排序。。。直到最后一次就是中位数。这个算法是O(n)的，再结合快排框架得到递推式根据主定理即得到复杂度，可能比较简略，见谅。

#include <cstdio> #include <algorithm> #include <random> using namespace std; int a[1000005]; int find_pivot(int r, int begin, int end) { int i = begin, j = end; while(i < j) { while(a[j] <= r && i < j) { j--; } while(a[i] >= r && i < j) { i++; } int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } a[begin] = a[i]; a[i] = r; return i; } //solution3 find_by_mid //冒泡排序 对不超过5个数排序 void normal_sort(int begin, int end) { for (int i = begin; i < end; i++) { for (int j = i + 1; j < end; j++) { if (a[i] < a[j]) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } } } //寻找中位数算法 int find_mid(int begin, int end) { if (begin == end) return a[begin]; int i; for (i = begin; i < end - 5; i += 5) { normal_sort(i, i + 5); //这里有个省内存的小技巧，直接把中位数已到begin的位置，因为a的顺序不重要 int tmp = a[i + 2]; a[i + 2] = a[begin + (i - begin) / 5]; a[begin + (i - begin) / 5] = tmp; } int surplus = (end - i + 1); int n = 0; //不是5的倍数，剩下的也排序，注意这个n的作用是记录到底有多少个中位数需要在下一轮排序 //如果surplus不是0，说明多一个 起到上取整的作用 if (surplus) { normal_sort(i, i + surplus); int tmp = a[i + surplus / 2]; a[i + surplus / 2] = a[begin + (i - begin) / 5]; a[begin + (i - begin) / 5] = tmp; n += 1; } if (n + (i - begin)/ 5 <= 1) return a[begin]; else return find_mid(begin, n + begin + (i - begin) / 5); } int findK_by_mid(int begin, int end, int k) { if (begin == end) return a[begin]; //找到中位数 int mid = find_mid(begin, end); //反向查找位置 int i; for (i = begin; i <= end; i++) { if (a[i] == mid) { break; } } //和快排一样了。。。 int r = a[i]; a[i] = a[begin]; a[begin] = r; int p = find_pivot(r, begin, end); if (p == k) return a[k]; else if (p > k) return findK_by_mid(begin, p - 1, k); else return findK_by_mid(p + 1, end, k); } int main(int argc, char *argv[]) { int n, k; while(scanf("%d%d", &n, &k) != EOF) { for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } //printf("%d\n", findK_by_sort(k, n)); //printf("%d\n", findK_by_quick(0, n - 1, k - 1)); printf("%d\n", findK_by_mid(0, n - 1, k - 1)); } return 0; }

横向比较

三种方法（第三行是第一种，第二行是第二种，第一行是第三种）的耗时分别如下，代码长度一样，因为我写在同一个文件里了。。。 可以看出solution2是最快的，solution3虽然理论很好，但是确实不够实用。