use*_*188 5 sorting algorithm selection
按顺序查找数组中k个最大元素的最快方法是什么(即从最大元素到第k个最大元素)？
tem*_*def 12
一种选择如下:
使用线性时间选择算法,如中位数或中位数,找到第k个最大元素并重新排列元素,使第k个元素前向的所有元素都大于第k个元素.
使用快速排序算法(如heapsort或quicksort)对第k个前向的所有元素进行排序.
步骤(1)花费时间O(n),步骤(2)花费时间O(k log k).总的来说,该算法在时间O(n + k log k)内运行,这非常非常快.
希望这可以帮助!
归档时间：
12 年，9 月 前
查看次数：
4613 次
最近记录：
6 年，8 月 前