⑵ 对n个元素进行起泡排序，在（ ）情况下比较的次数最少，其比较次数为（ ）。在（ ）情况下比较次数最多，其比较次数为（ ）。
⑸ 对n个待排序记录序列进行快速排序，所需要的最好时间是（ ），最坏时间是（ ）。 ⑹ 利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（ ）。
⑻ 对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（ ）的结点开始。
⑶ 对初始状态为递增有序的序列进行排序，最省时间的是（ ），最费时间的是（ ）。已知待排序序列中每个元素距其最终位置不远，则采用（ ）方法最节省时间。 A 堆排序 B插入排序 C快速排序 D 直接选择排序
⑸ 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（ ），就平均时间而言，（ ）最佳。
A 直接插入排序 B 起泡排序 C简单选择排序 D快速排序
⑹ 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（ ）方法最好。 A快速排序 B堆排序 C希尔排序 D 归并排序
⑸ 设有键值序列（k1, k2, …, kn），当i>n/2时，任何一个子序列（ki, ki+1,… , kn）一定是堆。 1．评价基于比较的排序算法的时间性能，主要标准是（ ）和（ ）。 5．排序趟数与序列的原始状态有关的排序方法是（ ）。 A 直接插入排序 B 简单选择排序 C 快速排序 D 归并排序
8. 如果只想得到一个序列中第k个最小元素之前的部分排序序列，最好采用什么排序方法？为什么？对于序列{57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7}，得到其第4个最小元素之前的部分序列{6,7,9,11}，使用所选择的排序算法时，要执行多少次比较？
【解答】采用堆排序最合适，依题意可知只需取得第k个最小元素之前的排序序列时，堆排序的时间复杂度Ο(n+klog2n)，若k≤nlog2n，则得到的时间复杂性是Ο(n)。
对于上述序列得到其前4个最小元素，使用堆排序实现时，执行的比较次数如下： 初始建堆：比较20次，得到6； 第一次调整：比较5次，得到7； 第二次调整：比较4次，得到9； 第三次调整：比较5次，得到11。