jieye の 数字花园

Search

Search IconIcon to open search

Last updated Unknown

不再全局排序,只对最大的 k 个排序

# 冒泡排序

image.png 冒泡是一个很常见的排序方法,每冒一个泡,找出最大值,冒 k 个泡,就得到 TopK 时间复杂度:O(nk)

# 堆排序

先用前 k 个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的 k 个元素,时间复杂度O(nlg(k)) image.png 接着,从第 k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的 k 个元素,总是当前最大的 k 个元素 image.png