6.6 各种内部排序算法比较及应用

6.6 各种内部排序算法比较及应用

选择题

　　1．选择题题目部分
　　● 对初始状态为递增序列的表按递增顺序排序，最省时间的是插入排序算法，最费时间的是 （1） 算法。
　　（1）A．堆排序 B．快速排序 C．插入排序 D．归并排序
　　● 若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 （2） 。
　　（2）A．快速排序 B．堆排序 C．归并排序 D．直接插入排序
　　● 在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列< Q,H,C,Y,P,A,M,S,R,D,F,X >中的关键码按字母的升序重新排列，则 （3） 是冒泡排序一趟扫描的结果， （4） 是初始步长为4的希尔排序一趟扫描的结果， （5） 是两路归并（合并）排序一趟扫描的结果， （6） 是以第一个元素为分界元素的快速排序一趟扫描的结果， （7） 是堆排序初始建堆的结果。
　　（3）A．H,C,Q,P,A,M,S,R,D,F,X,Y
　　　　 B．A,D,C,R,F,Q,M,S,Y,P,H,X
　　（4）A．F,H,C,D,P,A,M,Q,R,S,Y,X
　　　　 B．P,A,C,S,Q,D,F,X,R,H,M,Y
　　（5）A．H,Q,C,Y,A,P,M,S,D,R,F,X
　　　　 B．A,D,C,R,F,Q,M,S,Y,P,H,X
　　（6）A．F,H,C,D,P,A,M,Q,R,S,Y,X
　　　　 B．H,C,Q,P,A,M,S,R,D,F,X,Y
　　（7）A．H,C,Q,P,A,M,S,R,D,F,X,Y
　　　　 B．A,D,C,R,F,Q,M,S,Y,P,H,X
　　2．选择题练习的答案与分析
　　题号 （1）
　　答案 B
　　习题分析：
　　待排序列已有序，插入排序只进行一趟（n-1 次）比较，而快速排序的时间复杂度退化为O(n²)，堆和归并的时间复杂度仍为O(nlog₂ⁿ)。
　　题号 （2）
　　答案 C
　　习题分析：
　　先根据排序是否稳定可以排除选项A和B，在剩下的选项C和D算法中，直接插入排序的时间为O(n²)。插入排序、选择排序、冒泡排序和希尔排序时间复杂度是O(n²)，快速排序、堆排序和归并排序的时间复杂度为O(nlog₂ⁿ)。
　　题号 （3） （4） （5） （6） （7）
　　答案 　A　　B　　　A　　　A 　　B
　　习题分析：
　　冒泡排序可以是先比较A[n-1]和A[n-2]一直到A[0]，也可以先比较A[0]和A[1]一直到A[n-1]。对关键字序列< Q,H,C,Y,P,A,M,S,R,D,F,X >按照从后向前进行冒泡排序，可得序列为A，即（3）答案为A。
　　对关键字序列进行希尔排序，其中d=4，则（Q,P,R）排在一组，这需要对Q、P、R进行排序，排序得：P、Q、R。所以P应是序列的首字母，在（4）选项中，只有B满足要求。
　　二路归并排序只需要把待排序列顺次的每两个相邻元素分成一个小组，再使每个小组的元素有序即可。把题目中的数据进行分组有：< [Q,H],[C,Y],[P,A],[M,S],[R,D],[F,X] >，调整后得：< [H,Q],[C,Y],[A,P], [M,S],[D,R],[F,X] >。所以（5）正确答案为A。
　　快速排序对一个序列进行快速排序后有一个非常明显的特征，即“关键字前面的所有元素小于关键字，关键字后面的所有元素大于关键字”。我们往往能以此规则来快速又准确地得到正确答案。在此题中，以序列首字母Q为关键字，我们先看A，此选项满足上述特征。那是不是就能断定A是正确答案呢？只能说找到不合规则的选项将其排除，最终得到正确答案。而根据此原则，答案B不满足，因此（6）答案应选A。
　　建立堆的方法前面已经详细叙述了，（7）答案应该选B。
　　3．训练自测表（如表6-6所示）

表6-6 选择题练习自测表