题6

题6

题目

Q:就平均性能而言, 目前最好的内部排序算法是 ( ).
A. 冒泡排序 B. 直接插入排序 C. 希尔排序 D. 快速排序

分析

A:内部排序算法是指待排序的所有记录存放在内存中, 不涉及外存的排序算法。
最典型的不属于内部排序的算法是归并排序, 归并排序的时间复杂度是 ,但是归并排序需要额外的空间, 不适用于内部排序。
冒泡排序、直接插入排序、希尔排序的时间复杂度都是 ,而快速排序的时间复杂度是 。因此, 目前最好的内部排序算法是快速排序。

解

D
这里问的是平均性能,选项 的平均性能都会达到 ,而希尔排序虽然大大降低了直接插入排序的时间复杂度, 但其平均性能不如快速排序。另外, 虽然众多排序算法的平均时间复杂度也是 ,但快速排序算法的常数因子是最小的。