原文发表于：
之前聊过top-K问题，如下：
笔试面试题目：求top-K(使用堆)
有朋友反馈说，如果内存能容纳下这N个元素，那么使用堆处理top-K问题，并不是最佳算法。确实如此，在本文中，我们来循序渐进地看下top-K问题的处理思路。
排序法是最直接的算法，也是最容易想到的算法。使用快速排序，时间复杂度是O(N*logN). 以从大到小排序为例，top-K就a[0]到a[K-1].
然而，top-K问题本身并不要求要排序，所以快速排序显然做了很多无用功。来看看如下的改进。
直面问题，换一下思路，从矮子中选将军：
a. 先从N个数中选出最大的值；
b. 然后从剩余的N-1个数中选出最大的值；
c. 然后继续从剩余的N-2个数中选出最大的值；
......
依此类推，选择K次后，就选出top-K，显然，时间复杂度为O(N*K).
然而，我们注意到，在选择过程中，这K个数还是产生了排序的效果，做了一些无用功。来看看如下的改进。
使用堆选择法：
笔试面试题目：求top-K(使用堆)
使用堆之后，避免了对K个数进行排序，时间复杂度为O(N*logK)，显然，算法性能得到进一步优化。但是，这仍然不是最好的算法。且往下看。
我们首先来看这样一个问题：找出数组a[N]中第i大的值。
随机选择算法程序为：
#include <iostream> using namespace std; int partition(int a[], int low, int high) //划分 { int pivotKey = a[low]; while(low < high) { while(low < high && a[high] >= pivotKey) { high--; } a[low] = a[high]; while(low < high && a[low] <= pivotKey) { low++; } a[high] = a[low]; } a[low] = pivotKey; //恢复 return low; } // 找第i个最小的值 int randomSelect(int *a, int low, int high, int i) { if(low == high) { return a[low]; } int pivot = partition(a, low, high); int k = pivot - low + 1; if(k == i) // 刚好划出来了 { return a[pivot]; } if(i < k) // 缩小范围进行递归 { return randomSelect(a, low, pivot - 1, i); } return randomSelect(a, pivot + 1, high, i - k); // 缩小范围进行递归 } int main() { int a[] = {2, 5, 3, 1, 4, 111, 55}; int n = sizeof(a) / sizeof(a[0]); int i = 6; cout << randomSelect(a, 0, n - 1, i) << " " << endl; // 第i个最小值 return 0; }随机选择算法，借鉴了快速排序算法，使用了递归分治的思想。该算法的平均时间复杂度是O(N), 最坏时间复杂度是O(N^2).
平均时间复杂度如何证明？且看：
如果在极端情况下，时间复杂度恶化到O(N^2)，那该怎么办呢？有兴趣的朋友可以参考《算法导论》上的优化算法---快速选择算法，能将最坏时间复杂度优化为O(N).
在数组中，我们可以用O(N)时间复杂度找到第i大的数，那么类似地，我们自然很容易用O(N)时间复杂度来处理top-K问题。
本文再次讨论了top-K问题，并介绍了随机算法算法。最关键的，还是要体会算法的思路。
涛歌依旧 认证博客专家 排名第一 点链接学人工智能 公众号免费领资料 ❤️零基础入门进阶人工智能 ❤️欢迎关注涛哥公众号，免费领海量学习资料。涛哥：毕业后就职于华为和腾讯。微信：ai_taogeyijiu