top k

1、全部排序

2、快排

3、最小堆

取前k个建立一个最小堆,然后剩余的依次放进去和root比较,大于root,就放进去并扔掉root,重新调整最小堆。最后就是K个最大的数字。

4、分治法

将全部数据分成N份,前提是每份的数据都可以读到内存中进行处理,找到每份数据中最大的K个数。此时剩下N*K个数据,如果内存不能容纳N*K个数据,则再继续分治处理,分成M份,找出每份数据中最大的K个数,如果M*K个数仍然不能读到内存中,则继续分治处理。直到剩余的数可以读入内存中,那么可以对这些数使用快速排序的变形或者归并排序进行处理。

5、hash

原文地址:https://www.cnblogs.com/pacino12134/p/11251401.html