下载文档原格式
第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。
（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。
（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。
（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。
2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。
3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。
4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。
然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。
5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。
每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。
6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。
第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。
第10章 排序排序排序一、选择题 1．某内排序方法的稳定性是指．某内排序方法的稳定性是指( )( )( )。
【南京理工大学【南京理工大学 1997 1997 1997 一、一、一、101010（（2分）】 A ．该排序算法不允许有相同的关键字记录该排序算法不允许有相同的关键字记录 B B B．．该排序算法允许有相同的关键字记录记录C ．平均时间为0（n log n n log n）的排序方法）的排序方法）的排序方法D D D．以上都不对．以上都不对．以上都不对2．下面给出的四种排序法中下面给出的四种排序法中( )( )( )排序法是不稳定性排序法。
排序法是不稳定性排序法。
【北京航空航天大学北京航空航天大学 1999 1999 1999 一、一、10 10 （（2分）】 A. A. 插入插入插入 B. B. B. 冒泡冒泡冒泡 C. C. C. 二路归并二路归并二路归并 D. D. D. 堆积堆积堆积 3．下列排序算法中，其中（．下列排序算法中，其中（ ）是稳定的。
）是稳定的。
）是稳定的。
【福州大学【福州大学 1998 1998 1998 一、一、一、3 (23 (2分)】A. A. 堆排序，冒泡排序堆排序，冒泡排序堆排序，冒泡排序B. B. B. 快速排序，堆排序快速排序，堆排序快速排序，堆排序C. C. 直接选择排序，归并排序直接选择排序，归并排序直接选择排序，归并排序D. D. D. 归并排序，冒泡排序归并排序，冒泡排序归并排序，冒泡排序4．稳定的排序方法是（．稳定的排序方法是（ ）） 【北方交通大学【北方交通大学【北方交通大学 2000 2000 2000 二、二、二、33（2分）】 A ．直接插入排序和快速排序．直接插入排序和快速排序 B B B．折半插入排序和起泡排序．折半插入排序和起泡排序．折半插入排序和起泡排序C ．简单选择排序和四路归并排序．简单选择排序和四路归并排序D D D．树形选择排序和．树形选择排序和shell 排序排序5．下列排序方法中，哪一个是稳定的排序方法？（．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、88（2分）】A ．直接选择排序．直接选择排序B B B．二分法插入排序．二分法插入排序．二分法插入排序C C C．希尔排序．希尔排序．希尔排序D D D．快速排序．快速排序．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（．若要求尽可能快地对序列进行稳定的排序，则应选（A A ．快速排序．快速排序 B B B．归并排序．归并排序．归并排序 C C C．冒．冒泡排序）。
9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。
A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。
A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。
Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。
第十章排序一、名词解释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].key){r[j+1]=________;j--;}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<r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;}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<j){while((r[j].key>=x.key)&&(i<j)) ________;/*自尾端进行比较*/if(i<j){________;i++;/* 将r[j].kiy<x.key的记示移至i所指位置*/while((r[i].key<=x.key)&&(i<j))_ _______;/*自首行端进行比较*/if(i<j){________;j--;}/* 将r[j].kiy<x.key的记示移至j所指位置*/}}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<r [k].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两个有序序列（它们相应的关键字值满足K h <=…<=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．以下稳定的排序方法是（）①快速排序②冒泡排序③直接选择排序④ 堆排序4．以下时间复杂性不是O(n2)的排序方法是（）①直接插入排序②二路归并排序③冒泡排序④直接选择排序5．以下时间复杂性不是O(nlog2n)的排序方法是（）①堆排序② 直接插入排序③二路归并排序④快速排序6．在文件局部有序或文件长度较小的情况下，最佳的排序方法是（）①直接插入排序② 冒泡排序③ 直接选择排序④归并排序7．对于大文件的排序要研究在外设上的排序技术，即（）①快速排序法② 内排序法③外排序法④ 交叉排序法8．排序的目的是为了以后对已排序的数据元数进行（）操作。
①打印输出②分类③ 合并④查找9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（）①n-1 ②log2n③ 2log2n ④n210.快速排序在最坏的情况下的时间复杂度是（）①O(log2n) ②O(nlog2n)③ O(n2) ④O(n3)11.具有24个记录的序列，采用冒泡排序至少的比较次数是（）①1 ②23③ 24 ④ 52912．用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：25 84 21 47 15 27 6835 2015 20 21 25 47 27 6835 8415 20 21 25 35 27 4768 8415 20 21 25 27 35 4768 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 ④9122．在任何情况下，快速排序方法的时间性能总是最优的。
这种说法①正确②错误23．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（）方法。
①归并排序②直接插入排序③直接选择排序④快速排序。
四、简答及应用1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。
