第 9 章 排序
第10章排序
一、名词解释
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 if(i } } 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=________的结点k i k n/2,k n/2-1,k n/2-2,……为根的子树排成堆，直到以k 1为根的树排成堆，就完成了建 堆的过程。 18.堆排序是不稳定，空间复杂度为________。在最坏情况下，其时间复杂性也为________。 19.以下将a h ,…,a m 和a m+1,…,a n 两个有序序列（它们相应的关键字值满足 K h <=…<=K m ,K m+1<=…<=K n ）合并成一个有序序列R h ，…,R n （使其关键字值满足 K h <=…<=K n ）。请分析算法，并在________上填充适当的语句。 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(log 2n)。 ③堆排序的空间复杂度为O(n)。 ④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 2． 以下不稳定的排序方法是（ ） ①直接插入排序 ②冒泡排序 ③直接选择排序 ④二路归并排序 3． 以下稳定的排序方法是（ ） ①快速排序 ②冒泡排序 ③直接选择排序 ④ 堆排序 4．以下时间复杂性不是O(n2)的排序方法是（） ①直接插入排序②二路归并排序③冒泡排序④直接选择排序 5．以下时间复杂性不是O(nlog 2 n)的排序方法是（） ①堆排序② 直接插入排序③二路归并排序④快速排序6．在文件局部有序或文件长度较小的情况下，最佳的排序方法是（）①直接插入排序② 冒泡排序③ 直接选择排序④归并排序7．对于大文件的排序要研究在外设上的排序技术，即（） ①快速排序法② 内排序法③外排序法④ 交叉排序法8．排序的目的是为了以后对已排序的数据元数进行（）操作。 ①打印输出②分类③ 合并④查找9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（） ①n-1 ②log 2n ③ 2log 2 n ④n2 10.快速排序在最坏的情况下的时间复杂度是（） ①O(log 2n) ②O(nlog 2 n) ③ 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．在排序过程中，健值比较的次数与初始序列的排列顺序无关的是（）①直接插入排序和快速排序②直接插入排序和归并排序 ③直接选择排序和归并排序④快速排序和归并排序 14．（）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。 ①归并排序② 插入排序③快速排序④选择排序15（）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 ①归并排序②插入排序③ 快速排序④选择排序16．（）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。 ①归并排序②插入排序③快速排序④选择排序 17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（）方法能够最快地找出其中最大的正整数。 ①快速排序②插入排序③ 选择排序④ 归并排序18一般情况下，以下四种排序方法中，平均查找长度最小的是（） ①归并排序②快速排序③选择排序④插入排序19．以下四种排序方法中，要求附加的内存容量最大的是（） ①插入排序②选择排序③快速排序④归并排序20已知一个链表中有3000个结点，每个结点存放一个整数，（）可用于解决这3000个整数的排序问题且不需要对算法作大的变动。 ①直接插入排序法②简单选择排序方法 ③快速排序方法④堆排序方法 21．若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（）次比较。 ①33 ②45 ③70 ④91 22．在任何情况下，快速排序方法的时间性能总是最优的。这种说法 ①正确②错误 23．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（）方法。 ①归并排序②直接插入排序 ③直接选择排序④快速排序。 四、简答及应用 1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。 2．举例说明本章介绍的各排序方法中那些是不稳定的？ 3．相对于树形选择排序，直接选择排序和堆排序有何优点？ 4．试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。 5．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。 （1）（3，10，12，22，36，18，28，40）； （2）（5，8，11，15，23，20，32，7）。 6．对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。 7．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。 五、算法设计 1．设计一个用链表表示的直接选择排序算法。 2．写出非递归调用的快速排序算法。 3．插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序方法。 4．一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。 5．已知（k 1,k 2 ……，k n ）是堆，试写一个算法将（k 1 ,k 2 ,……，k n ,k n+1 ）调整 为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个k n+1 后应从叶子向根的方向调整）。 6．设计一个用链表表示的直接插入排序算法。