首页 > 试题广场 >

设有5000个待排序的记录关键字,如果需要用最快的方法选出其

[单选题]

设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列()方法可以达到此目的。

  • 快速排序
  • 堆排序
  • 归并排序
  • 插入排序
快排是不行,但是快排的partition函数可以做到。复杂度为n,但是取出来的10个最小的关键字无序,题目也没要求有序
发表于 2017-07-24 16:47:27 回复(0)
分析: 9 快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的 10 个数,而堆排序只需要在初始堆的基础上再进行 10 次筛选即可,每次筛选的时间复杂度为 O(log2n)
发表于 2017-05-16 22:58:10 回复(1)
快排需要nlogn,堆需要n
发表于 2019-03-15 14:25:28 回复(0)