第十章 排序

第十章 排序

一、名词解释

1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序

二、填空

1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。

2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。

3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。

4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。 5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。

void straightsort(list r);

{for(i=___________;i<=n;i++)

{r[0]=r[i];j=i-1;

while(r[0].key

r[j+1]=_______;

}

}

7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。

8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag为特征位，定义为布尔型*/ {for(i=1;i<=________;i++) {_______________;

for(j=1;j<=_________;j

++)

if(r[j+1].key

if(flag) return; } }

9.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。

10.以下对r[h],r[h+1],??r[p]子序列进行一趟忆速排序。请分析算法，并在________上填充适当的语句。

int quickpass(list r,int h,int p)

{i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i

{while((r[j].key>=x.key)&&(i

{________;i++;/* 将r[j].kiy

while((r[i].key<=x.key)&&(i

if(i

r[j].kiy

} }

r[i]=________;return(i);/*一趟快速 排序结束，将x移至正确的位置*/ }

11.对快速排序来讲，其最好情况下的时间复杂度是________，其最坏情况下的时间复杂度是________。 12.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。 void select(list r,int n)

{for(i=1;i<=________;i++)/*每

次循环，选择出一个最小键值*/ {k=i;

for(j=i+1;j<=n;j++)if(r[j].key

if(______)swap(r[k],r[i]）;/*函数swap(r[k],r[i]）交换r[k]和r[i]的位置*/ } }

13.直接选择排序是不稳定的，其时间复杂性为________。

14.树形选择排序要增加________个结点以保存前面比较的结果。另外，排序的结果还需要另外开辟________.

15.树形选择排序可用一棵树来表示这一排序过程，树中的n个叶子代表待排序记录的键值，叶子上面一层是________两两比较的结果，依次类推。________表示最后选择出来的最小关键字。在选择次最小键值时，只需将叶结点中最小键值改成________，重新进行比较。依次类推。

16.若树形选择排序的叶子数为n，除第一次需执行________次比较就选择出一个最小的键值外，以后的每次都只经过________次比较就选择出一个最小的键值。所以树形选择排序总的时间开销为________。

17.从一个无序序列建立一个堆的方法是：首先将要排序的所有键值分放到一棵________的各个结点中，然后

从i=________的结点ki开始，逐步把以kn/2,kn/2-1,kn/2-2,??为根的子树排成堆，直到以k1为根的树排成堆，就完成了建堆的过程。

18.堆排序是不稳定，空间复杂度为________。在最坏情况下，其时间复杂性也为________。

19.以下将ah,?,am和am+1,?,an两个有序序列（它们相应的关键字值满足Kh<=?<=Km,Km+1<=?<=Kn）合并成一个有序序列Rh，?,Rn（使其关键字值满足Kh<=?<=Kn）。请分析算法，并在________上填充适当的语句。 void merge(list a,list R,int h,int m,int n) {i=h;k=h;j=m+1; while((i<=m)&&(j<=n))

{if(a[i].key<=a[j].key){R[k]=________;________;}

else{R[k]=________;________;} k++; }

while(i<=________){R[k]=a[i];i++;k++;}

while(j<=________){R[k]=a[j];j++;k++;} }

此算法的执行时间为________.

20．归并排序要求待排序列由若干个___________的子序列组成。 21．二路归并排序的时间复杂度是___________。

22．对于n个记录的集合进行归并排序，所需的附加空间消耗是___________。

23.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。 24．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序进行排序，最省时间的是___________算法，最费时间的是___________算法。 三、单项选择

1． 以下说法错误的是 （ ） ①直接插入排序的空间复杂度为O(1)。

②快速排序附加存储开销为O(log2n)。 ③堆排序的空间复杂度为O(n)。 ④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。

2． 以下不稳定的排序方法是 （ ） ①直接插入排序 ②冒泡排序 ③直接选择排序 ④二路归并排序

3． 以下稳定的排序方法是 （ ）

①快速排序 ②冒泡排序 10.快速排序在最坏的情况下的时间③直接选择排序 ④ 堆排序 4． 以下时间复杂性不是O(n2

)的排序

方法是 （ ） ①直接插入排序 ②二路归并排序 ③冒泡排序 ④直接选择排序

5． 以下时间复杂性不是O(nlog2n)的排序方法是 （ ）

①堆排序 ② 直接插入排序 ③二路归并排序 ④快速排序

6． 在文件局部有序或文件长度较小的情况下，最佳的排序方法是

（ ）

①直接插入排序 ② 冒泡排序

③ 直接选择排序 ④归并排序

7． 对于大文件的排序要研究在外设

上的排序技术，即

（ ）

①快速排序法 ② 内排序法

③外排序法 ④ 交叉排序法

8．排序的目的是为了以后对已排序的数据元数进行（ ）操作。

①打印输出 ②分类

③ 合并 ④查找

9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次

数为（ ）

①n-1 ②log2n

③ 2log22n ④n

复杂度是

（ ）

①O(log2n) ②O(nlog2n) ③ O(n2) ④O(n3) 11.具有24个记录的序列，采用冒泡排序至少的比较次数是 （ ）

①1 ②23 ③ 24 ④ 529 12．用某种排序方法对序列（25，84，

21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下： 25 84 21 47 15 27 68

35 20 15 20 21 25 47 27 68 35 84

15 20 21 25 35 27 47 68 84

15 20 21 25 27 35 47 68 84 则采取的排序方法是 （ ） ①直接选择排序 ②冒泡排序 ③快速排序 ④二路归并排序

13．在排序过程中，健值比较的次数与初始序列的排列顺序无关的是

（ ） ①直接插入排序和快速排序 ②直接插入排序和归并排序

③直接选择排序和归并排序 ④快速排序和归并排序