寻找n个元素里面最大的k个数top k算法

June 10, 2021 | 0 Minute Read

1. 采用堆 时间复杂度 O(n+klog n)
2. qsort + selection sort，快速排序 每轮丢掉另外一半只处理直接想要的k的范围内的那一边，但partition足够小时使用选择排序。 时间复杂度 O(n + k log k)
3. Knuth’s Art of Programming, Volume 3, Page 212 的“tournament method” ，类似单场淘汰赛，两两分组决出最后的胜者，然后比赛完成之后从冠军的比赛路径（树）的反向搜索，从冠军在这些对手也用类似一对一比赛的方法找到第二个最大值，一直到找到k个最大值为止。时间复杂度说是O(n - k + (k-1) [log (n-k+2)] )，但可能结构比较复杂
4. c++ 里面有一个std::partial_sort 函数，看起来用这个就好了

https://en.wikipedia.org/wiki/Partial_sorting

https://en.cppreference.com/w/cpp/algorithm/partial_sort

Since k is small, you can use the tournament method to find the kth largest. This method is described in Knuth’s Art of Programming, Volume 3, Page 212 https://stackoverflow.com/questions/4956593/optimal-algorithm-for-returning-top-k-values-from-an-array-of-length-n