如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列 用()方法最快。【清华
序列,元素,最小
已帮助 人
如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列,用()方法最快。【清华大学1998一、2(2分)】
A.起泡排序
B.快速排列
C.Shell排序
D.堆排序
E.简单选择排序
请帮忙给出正确答案和分析,谢谢!
热搜:sd序列是5端互补序列
-
正确答案:D
本题相当于从n个元素选取k(k<<n)个元素用什么排序方法最好。起泡排序和简单选择排序第1趟比较n一1次选出最小/最大元素,第2趟比较n一2次,选出次小/次大元素,因此,这两种排序方法不予考虑。若选最小,快速排序和起泡排序差不多。希尔排序只有等排序结束才能有最后结果,这里不予考虑。堆排序建堆选出最小/最大元素,比较了至多不超过4n次,以后每选出一个元素需要logn次的比较。由此,本题的答案应该选D。但是编者还有另外的分析。若先用快速排序选出第k个最小元素,则比较次数在O(n)级,算法见下面“五、27”。对
