题15
题目
Q:【2012 统考真题】在内部排序过程中, 对尚未确定最终位置的所有元素进行一遍处理 称为一趟排序.
下列排序算法中, 每趟排序结束都至少能够确定一个元素最终位置的方法是 ( ).
I. 简单选择排序
II. 希尔排序
III. 快速排序
IV. 堆排序
V. 二路归并排序
A. 仅 I、III、IV
B. 仅 I、III、V
C. 仅 II、III、IV
D. 仅 III、IV、V
分析
A:1肯定有，3肯定也有，归并不好说
解
A
对于 I, 简单选择排序每次选择未排序序列中的最小元素放入其最终位置。
对于 II, 希尔排序每次对划分的子表进行排序, 得到局部有序的结果, 所以不能保证每趟结束都能确定一个元素的最终位置。
对于 III, 快速排序每趟结束后都将枢轴元素放到最终位置。
对于 IV, 堆排序属于选择排序,每次都将大根堆的根结点与表尾结点交换,确定其最终位置。
对于