不再全局排序,只对最大的 k 个排序
# 冒泡排序
冒泡是一个很常见的排序方法,每冒一个泡,找出最大值,冒 k 个泡,就得到 TopK
时间复杂度:O(nk)
# 堆排序
先用前 k 个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的 k 个元素,时间复杂度O(nlg(k))
接着,从第 k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的 k 个元素,总是当前最大的 k 个元素

Search
不再全局排序,只对最大的 k 个排序
冒泡是一个很常见的排序方法,每冒一个泡,找出最大值,冒 k 个泡,就得到 TopK
时间复杂度:O(nk)
先用前 k 个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的 k 个元素,时间复杂度O(nlg(k))
接着,从第 k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的 k 个元素,总是当前最大的 k 个元素
