BFPRT 算法(TOP-K问题)
直接利用快排思想不就完了吗,分组干什么?
假如我们要求top 5小。快排跑一趟的结果是我们选取的pivot这个数所处的位置一定就是最终排完序的位置,假设这个位置为j,而且pivot左边的数都小于它,右边的数都大于它。
if j == 5,那直接结束了,pivot左边的数都是top 5。
if j > 5, 表示top 5全在左边,那左边再跑快排,一直到某一趟pivot的位置恰好等于5。
这个比快排省掉的就是只需要单侧递归
来源: http://blog.jobbole.com/112753/