（1） （2） （3） （4）

内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。 基数排序的设计思想是依照对关键字的比较来实施的。

用希尔（Shell）方法排序时，若关键字的初始排序杂乱无章，则排序效率就低。

当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复

杂度的主要因素。

（5）对一个堆，安二叉树层次进行遍历可以得到一个有序序列。

答：(1) 错误。快速排序在待排序记录关键字为随机分布时效果最好，基本有序时效果最差。

(2)错误。基数排序不进行关键字值的比较。 (3)错误。希尔排序法与关键字初始序列有序或无序无关。 （4）正确。 （5）错误。

3.某整型数组R的10个元素值依次为{6，2，9，7，3，8，4，5，0，10}。用下列各排序方法，将A中元素由小到大排序。

（1）取第一个元素6作为划分数据，试写出快速排序第一次划分操作后R中的结果。

（2）用堆排序（用大根堆），试写出将第一个选出的数据放在A的最后位置上，将A调整成堆后的A中结果。（3）用基数为3的基数排序法，试写出第一次分配和收集后A中的结果。 答：（1）快速排序第一次分隔过程如下： void Partition(RecType R[],int n) {

RecType temp; int i,j; i=0,j=n-1; temp= R[i]; while(i!=j) {

while(j>i && R[j]>temp) j--; if(i

while(itemp) i++; if(i

R[i]=temp; }

其划分过程如下（数序中第1个带方框的数由i指向，第2个带方框的数由j指向）。 temp=6; 初始序列：

（6），2，9，7，3，8，4，5，0，（10）

第1次循环： （6），2，9，7，3，8，4，5，（0），10 —>（0），2，9，7，3，8，4，5，（0），10

21

/*从左向右扫描，找第1个关键字大于temp的记录R[i] */

/*表示找到这样的R[i]，R[i] 、R[i]交换*/

R[i]=R[j]; i++;

/*从右向左扫描，找第1个关键字小于temp的记录R[j]*/

/*表示找到这样的R[j]，R[i]、 R[j]交换*/

/*用区间的第1个记录作为基准*/

/*从区间两端交替向中间扫描，直至i=j为止*/

0，2，（9），7，3，8，4，5，（0），10 —>0，2，（9），7，3，8，4，5，（9），10 0，2，5，（7），3，8，4，（5），9，10 —>0，2，5，（7），3，8，4，（7），9，10 0，2，5，4，3，（8），（4），7，9，10 —>0，2，5，4，3，（8），（8），7，9，10

第2次循环： 0，2，（9），7，3，8，4，（5），9，10 —>0，2，（5），7，3，8，4，（5），9，10 第3次循环： 0，2，5，（7），3，8，（4），7，9，10 —>0，2，5，（4），3，8，（4），7，9，10

22