《第9章内部排序》习题解答

《数据结构》第九章习题参考答案《数据结构》第九章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、快速排序是一种稳定的排序方法。

（×）2、在任何情况下，归并排序都比简单插入排序快。

（×）3、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。

（√）4、内排序要求数据一定要以顺序方式存储。

（×）5、直接选择排序算法在最好情况下的时间复杂度为O（n）。

( ×)6、快速排序总比简单排序快。

( ×)二、单项选择题1．在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）。

A．直接插入排序B．直接选择排序C．快速排序D．归并排序2．下列排序方法中，哪一个是稳定的排序方法？（B）A．直接选择排序B．折半插入排序C．希尔排序D．快速排序3、比较次数与排序的初始状态无关的排序方法是( B)。

A．直接插入排序B．起泡排序（时间复杂度O（n2））C．快速排序D．简单选择排序4、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 则采用的排序是( A)。

A. 选择B. 冒泡C. 快速D. 插入5、快速排序方法在（D）情况下最不利于发挥其长处。

A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序6、用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序，各趟排序结束时的结果为：（基准）20，21，15，25，84，27，68，35，47（25）15，20，21，25，47，27，68，35，84（左20右47）15，20，21，25，35，27，47，68，84（左35右68）15，20，21，25，27，35，47，68，84 ；则采用的排序方法为（C）。

第9章内部排序一、问答题1. 什么是内部排序？什么是排序方法的稳定性？2. 对于本章介绍的内部排序方法，哪几种是稳定的？哪几种是不稳定的？对不稳定的排序方法试举例说明。

3. 对于给定的一组记录的关键字：23，13，17，21，30，60，58，28，30，90。

试分别写出用下列排序方法对其进行排序时，每一趟排序后的结果：(1)直接插入排序；(2)希尔排序；(3)冒泡排序；(4)直接选择排序；(5)快速排序(6)堆排序(7)归并排序。

4. 对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这n个元素的初始序列。

(1)n = 8时，在最好的情况下需要进行多少次比较？试说明理由。

(2)给出n = 8时的一个最好情况的初始排列实例。

5 试为下列各种情况选择合适的排序方法：(1)n = 30，要求在最坏的情况下，排序速度最快；(2)n = 30，要求排序速度既要快，又要排序稳定。

6. 判别以下序列是否为堆（所有的非叶子结点的关键字值k i均不大于其左右两个分支结点的关键字值k2和k2i+1。

），如果不是，则把它调整为堆。

(1)( 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 )；(2)( 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 )；(3)( 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 )；(4) ( 05, 56, 20, 03, 23, 40, 38, 29, 61, 05, 76, 28, 100 )。

7. 一组待排序记录的关键字是：986，321，123，432，500，654，018，765，987，210。

按照LSD方法写出基数排序的过程和结果。

8. 试证明：如果对于一个长度为n的任意文件进行排序，则至少需进行nlog2n次比较。

9. 试构造对5个整数元素进行排序，最多只用7次比较的算法思想。

习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D.简单选择排序E. 起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为 O(n?n) 的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（ 84， 47， 25， 15， 21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21（2） 15 47 25 84 21（3） 15 21 25 84 47（4） 15 21 25 47 84则采用的排序是 ()。

A. 选择B.冒泡C.快速D.插入4．下列排序算法中 ( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B.冒泡C.归并D.堆5．一组记录的关键码为（46，79，56， 38，40， 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A． (38,40,46,56,79,84) B. (40,38,46,79,56,84)C． (40,38,46,56,79,84) D. (40,38,46,84,56,79)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。

A．冒泡 B. 希尔C. 快速D. 堆7.就平均性能而言，目前最好的内排序方法是() 排序法。

A. 冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A. 归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列 {10,14,26,29,41,52}从大到小排序，需进行（）次比较。

习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D. 简单选择排序E. 起泡排序F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为O(n?n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序3．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21（3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是 ( )。

A. 选择B. 冒泡C. 快速D. 插入4．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B. 冒泡C. 归并D. 堆5．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

A．冒泡 B. 希尔 C. 快速 D. 堆7. 就平均性能而言，目前最好的内排序方法是( )排序法。

A. 冒泡B. 希尔插入C. 交换D. 快速8. 下列排序算法中，占用辅助空间最多的是：( )A. 归并排序B. 快速排序C. 希尔排序D. 堆排序9. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。

3. 将R[j+1]=R[0] 实现整个序列的排序。
North China Electric Power University
排序算法如下：
void insort(List r, int n) {//r为给定的表，其记录为r[i]，i=0，1，…，n，x为暂存单元。 for (i=2; i<=n; i++) { r[0]=r[i]; //r[0]作为标志位 j=i-1; while (r[0].key<r[j].key) { r[j+1]=r[j]; j--; } //j从i-1至0，r[j].key与r[i].key进行比较 r[j+1]=r[0]; } }//insort
North China Electric Power University
例如：
第二趟希尔排序，设增量d = 3
第三趟希尔排序，设增量d = 1
North China Electric Power University
希尔排序的算法描述如下:
void ShellInsert (List r,int d) //本算法对直接插入算法作了以下修改： // 1. 前后记录位臵的增量是d，而不是1； // 2. r[0]只是暂存单元，不是哨兵。当j<=0时，插入位臵已找到。 for (i=2;i<= n ; i++) { { r[0]=r[i]; for(i=d+1;i<=n;i++) j=i-1; if ( r[i] < r[i-d]) //需将r[i]插入有序增量子表 while ( r[0].key<r[j].key) { r[0] = r[i]; //暂存在R[0] { r[j+1]=r[j]; j=i-d ; j=j-1; while ((j>0) and (r[0] < r[j])) } { r[j+d] = r[j]; //记录后移，查找插入位臵 r[j+1]=r[0]; j=j-d; } } r[j+d] = r[0];//插入 } }

void BInsertSort(SqList &L) { // 对顺序表L作折半插入排序。算法10.2 for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0] low=1; high=i-1; while(low<=high) { // 在r[low..high]中折半查找有序插入的位置 m=(low+high)/2; // 折半 if LT(L.r[0].key,L.r[m].key) high=m-1; //插入点在低半区 else low=m+1; // 插入点在高半区 } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; // 记录后移 L.r[high+1]=L.r[0]; // 插入 } }
第9章 内部排序
为了讨论方便，假设待排记录的关键字均为整数，均从 数组中下标为1的位置开始存储，下标为0的位置存储监视哨， 或空闲不用。 typedef int KeyType; typedef struct { KeyType key; OtherType other-data; } RecordType;
类: 一类是整个排序过程完全在内存中进行，称为内部排序； 另一类是由于待排序记录数据量太大，内存无法容纳全部数 据， 排序需要借助外部存储设备才能完成，称为外部排序。
第9章 内部排序
假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)， 若在排序前的序列中Ri
领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj， 则 称所用的排序方法是稳定的；反之，当相同关键字的领先关系 在排序过程中发生变化，则称所用的排序方法是不稳定的。 无论是稳定的还是不稳定的排序方法，均能排好序。在应 用排序的某些场合，如选举和比赛等，对排序的稳定性是有特 殊要求的。

1、以下关于排序的叙述中正确的是（）。

A.排序方法都是在顺序表上实现的，在链表上无法实现排序方法B.稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高C.在顺序表上实现的排序方法在链表上也同样适合D.对同一个顺序表使用不同的排序方法进行排序，得到的排序结果可能不同正确答案：D解析： D、稳定的排序方法的效率不一定都比不稳定的排序方法高。

有些排序方法既可以上顺序表上实现，也可以在链表上实现，但不是所有的排序方法都如此。

由于排序方法具有不同的稳定性，所以对同一个顺序表（存在相同的多个关键字记录）使用不同的排序方法进行排序，得到的排序结果可能不同。

2、以下不属于内排序方法的是（）。

A.直接插入排序B.拓扑排序C.二路归并排序D.堆排序正确答案：B解析： B、拓扑排序是一种产生拓扑序列的方法，不属内排序方法。

3、目前来讲，基于比较的内排序方法最好的平均时间复杂度为（）。

A. O(log2n)B. O(n2)C. O(nlog2n)D. O(n)正确答案：C解析： C、目前来讲，基于比较的内排序方法最好的平均时间复杂度为O(nlog2n)。

4、对有n个记录的表进行直接插入排序，在最好情况下需比较（）次关键字。

A.n(n-1)/2B.n-1C.n/2D.n+1正确答案：B解析： B、直接插入排序在初始数据正序时效率最好，此时只需要n-1次关键字比较。

5、数据序列{8，9，10，4，5，6，20，1，2}只能是（）算法的两趟排序后的结果。

A.堆排序B.简单选择排序C.冒泡排序D.直接插入排序正确答案：D解析： D、采用排除法，因为两趟排序后结果中的有序区不是全局有序的，所以只能是直接插入排序，不可能是其他三种排序方法。

6、对数据序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排序变为{4，9，-1，8，20，7，15}，则采用的是（）算法。

A.冒泡排序B.希尔排序C.快速排序D.简单选择排序正确答案：B解析： B、因为一趟排序后结果中的有序区不是全局有序的，所以不可能是简单选择排序和冒泡排序。

置上。
A 归并排序
B 插入排序
C 快速排序
D 选择排序
17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（ ）
方法能够最快地找出其中最大的正整数。
A 快速排序
B 插入排序
C 选择排序
D 归并排序
18 一般情况下，以下四种排序方法中，平均查找长度最小的是
（）
A 归并排序
B 快速排序
1a直接插入排序序号101112关键字834063138435965739796115408363138435965739796115406383138435965739796115134063838435965739796115134063838435965739796115133540638384965739796115133540638384965739796115133540576383849639796115133539405763838496796115101335394057637983849661151113353940576163798384961512131535394057616379838496直接选择排序序号101112关键字8340631384359657397961151340638384359657397961151315638384359657397961401315358384639657397961401315353984639657837961401315353940639657837961841315353940579663837961841315353940576163837996841315353940576163837996841315353940576163798396841013153539405761637983968411131535394057616379838496快速排序关键字834063138435965739796115第一趟排序后154063136135795739839684第二趟排序后131563406135795739838496第三趟排序后131539406135576379838496第四趟排序后131535396140576379838496第五趟排序后131535395740616379838496第六趟排序后131535394057616379838496第七趟排序后131535394057616379838496堆排序关键字

《数据结构》习题汇编09-第九章-排序-试题数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A. 起泡排序B. 快速排序C. 直接选择排序D. 堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（）。

A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A. 8B. 10C. 15D. 255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序7.下列排序算法中（）算法是不稳定的。

A. 起泡排序B. 直接插入排序C. 基数排序D. 快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是（）。

A. 3B. 4C. 5D. 69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。

A. 5B. 6C. 7D. 810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。

A. 起泡排序B. 希尔排序C. 快速排序D. 直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。

A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

1、以下关于排序的叙述中正确的是（）。

A.排序方法都是在顺序表上实现的，在链表上无法实现排序方法B.稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高C.在顺序表上实现的排序方法在链表上也同样适合D.对同一个顺序表使用不同的排序方法进行排序，得到的排序结果可能不同正确答案：D解析： D、稳定的排序方法的效率不一定都比不稳定的排序方法高。

有些排序方法既可以上顺序表上实现，也可以在链表上实现，但不是所有的排序方法都如此。

由于排序方法具有不同的稳定性，所以对同一个顺序表（存在相同的多个关键字记录）使用不同的排序方法进行排序，得到的排序结果可能不同。

2、以下不属于内排序方法的是（）。

A.直接插入排序B.拓扑排序C.二路归并排序D.堆排序正确答案：B解析： B、拓扑排序是一种产生拓扑序列的方法，不属内排序方法。

3、目前来讲，基于比较的内排序方法最好的平均时间复杂度为（）。

A. O(log2n)B. O(n2)C. O(nlog2n)D. O(n)正确答案：C解析： C、目前来讲，基于比较的内排序方法最好的平均时间复杂度为O(nlog2n)。

4、对有n个记录的表进行直接插入排序，在最好情况下需比较（）次关键字。

A.n(n-1)/2B.n-1C.n/2D.n+1正确答案：B解析： B、直接插入排序在初始数据正序时效率最好，此时只需要n-1次关键字比较。

5、数据序列{8，9，10，4，5，6，20，1，2}只能是（）算法的两趟排序后的结果。

A.堆排序B.简单选择排序C.冒泡排序D.直接插入排序正确答案：D解析： D、采用排除法，因为两趟排序后结果中的有序区不是全局有序的，所以只能是直接插入排序，不可能是其他三种排序方法。

6、对数据序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排序变为{4，9，-1，8，20，7，15}，则采用的是（）算法。

A.冒泡排序B.希尔排序C.快速排序D.简单选择排序正确答案：B解析： B、因为一趟排序后结果中的有序区不是全局有序的，所以不可能是简单选择排序和冒泡排序。

插入排序
插入排序
• 以上述静态链表类型作为待排记录序列的存储结构，并设 数组中下标为0的分量为表头结点，并令表头结点记录的关 键码取最大整数MAXNUM。 • 表插入的排序过程是，首先将静态链表中数组下标为1的分 量（结点）和表头结点构成一个循环链表，然后依次将下 标为2～n的分量（结点）按记录关键码非递减有序插入到 循环链表中，算法如以下程序所示。
插入排序
例9-3
• 以关键码序列{52, 43, 68, 89, 77, 16, 24, 52*, 80, 31}为例，表 插入排序的过程如下列图所示。
插入排序
• 从上面的过程可看出，表插入排序与直接插入排序的不同 之处在于，表插入排序以修改2n次指针值来代替记录的移 动，但和关键码的比较次数相同，因此表插入排序的时间 复杂度仍为O(n2)。
i=n
交换排序
• 快速排序 • 快速排序（quick sort）是Hoare于1962年提出的一种分区交 换排序。它采用了一种分而治之的策略，是对冒泡排序的 一种改进。其算法思想是，首先将待排序记录序列中的所 有记录作为当前待排序区域，选取第一个记录的关键码值 为基准（轴值），从待排序记录序列左、右两端开始向中 间靠拢，交替与轴值进行比较，若左侧记录的关键码值大 于轴值，则将该记录移到基准记录的右侧，若右侧记录的 关键码值小于轴值，则将该记录移到基准记录的左侧，最 后让基准记录到达它的最终位置，此时，基准记录将待排 序记录分成了左右两个区域，位于基准记录左侧的记录都 小于或等于轴值，位于基准记录右侧的所有记录的关键码 都大于或等于轴值，这就是一趟快速排序。
例9-5
• 如图所示为冒泡排序的一个示例。冒泡排序的效率分析： ① 若初始序列为“正序”序列，则只需进行一趟排序，在 排序过程中进行n−1次关键码的比较，且不移动记录；② 若 初始序列为“逆序”序列，则需进行n−1趟排序，需进行 2 ∑ (i − 1) = n(n − 1) / 2次比较。因此，总的时间复杂度为O(n2)。

第9章排序习题答案1. 假设含n个记录的序列为{ R1, R2, …，R n}，其相应的关键字序列为{ K1, K2, …，K n}，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ks n，按此固有关系将n个记录序列重新排列为{ Rs1, Rs2, …，Rs n }。

若整个排序过程都在内存中完成，则称此类排序问题为内部排序。

2.3. 直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。

即将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i] ，最终使整个文件有序。

共进行n-1趟插入。

最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。

简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1<=i<n)趟简单选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。

共进行n-1趟选择。

最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是不稳定排序。

二路并归排序的基本思想是基于归并，开始将具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到⎡n/2⎤个长度为2的有序序列，再进行两两归并，得到⎡n/4⎤个长度为4的有序序列。

如此重复，经过⎡log2n⎤趟归并，最终得到一个长度为n的有序序列。

最坏时间复杂度和平均时间复杂度都是0(nlog2n)，空间复杂度是O(n)，是稳定排序。

4. 错误。

快速排序，堆排序和希尔排序是时间性能较好的排序方法，但都是不稳定的排序方法。

5. (1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序6. 不是。

数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A. 起泡排序B. 快速排序C. 直接选择排序D. 堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（）。

A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A. 8B. 10C. 15D. 255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序7.下列排序算法中（）算法是不稳定的。

A. 起泡排序B. 直接插入排序C. 基数排序D. 快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是（）。

A. 3B. 4C. 5D. 69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。

A. 5B. 6C. 7D. 810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。

A. 起泡排序B. 希尔排序C. 快速排序D. 直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。

A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

一、单选题1、对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，5，2，37)B.(19，21，37，5，2)C.(19，21，2，5，37)D.(19，21，5，37，2)正确答案：B2、对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，37，5，2)B.(19，21，2，5，37)C.(19，21，5，37，2)D.(19，21，5，2，37)正确答案：D3、对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（）。

A.(113，165，176，197，127，138，149)B.(113，165，176，127，197，138，149)C.(113，127，138，149，165，176，197)D.(149，138，165，197，176，113，127)正确答案：A4、下列各项键值（）序列不是堆的。

A.(5，23，68，16，94)B.(5，23，16，94，68)C.(5，16，23，68，94)D.(5，23，16，68，94)正确答案：A5、假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（）是归并排序的过程。

A.(24，62，36，19)(24，36，62，19)(19，24，36，62)B.(24，62，19，36)(19，24，36，62)C.(62，24，36，19)(19，24，36，62)D.(24，19，36，62)(24，19，36，62)(19，24，36，62)正确答案：B6、在第一趟排序之后，不能确保将数据表中某一个元素放在其最终位置上的排序算法是（）。

A.归并排序B.快速排序C.冒泡排序D.选择排序正确答案：A7、对于下列排序，（）的时间效率与关键字初始序列有直接关系。

算法步骤： （1）将整个待排序的记录序列划分成有序 区和无序区，初始时有序区为待排序记 录序列的第一个记录，无序区包括所有 剩余待排序的记录； （2）将无序区的第一个记录插入到有序 区的合适位置中，从而使无序区减少一 个记录，有序区增加一个记录； （3）重复执行（2），直到无序区中没有 记录为止。
希尔排序算法： void shell_sort(Sqlist *L, int dk[], int t)
/*按增量序列dk[0 … t-1],对顺序表L进行希尔排序*/
{ int m ; for (m=0; m<=t; m++) shell_pass(L, dk[m]) ; }
希尔排序可提高排序速度： (1) 分组后n值减小，n² 更小，而T(n)=O(n² ), 所以T(n)从总体上看减小了； (2) 关键字较小的记录可以以增量为单位跳 跃式前移，当进行最后一趟增量为1的插 入排序时，序列已基本有序。 增量序列取法： (1) 无除1以外的公因子； (2) 增量递减，最后一个增量值必须为1。
算法分析：
⑴ 最好情况：待排序记录按关键字从小到大排 列，算法中的内循环无须执行，每一趟排序时， 关键字比较1次，记录不需移动。所以整个排 序的关键字比较次数为n-1，记录移动次数为 0。 ⑵ 最坏情况：待排序记录按关键字从大到小排 列，每一趟排序时，算法中的内循环体执行i-1 次，关键字比较次数i次，记录移动次数i+1。 一般地，认为待排序的记录在各个位置的插入 概率相同，则取以上两种情况的平均值，作为 排序的关键字比较次数和记录移动次数，约为 n2/4，由此，直接插入排序的平均时间复杂度 为O(n2)。
插入排序
插入排序是一类借助“插入”操作进行 排序的方法，其主要思想是：每次将一 个待排序的记录按其关键字的大小插入 到一个已经排好序的有序序列中，直到 全部记录排好序。

第9章习题答案第9章排序习题91.在各种排序方法中，哪些是稳定的？哪些是不稳定的？对不稳定的排序方法举出一个不稳定的例子。

解：排序方法直接插入排序折半插入排序二路插入排序表插入排序起泡排序直接选择排序希尔排序快速排序堆排序 2-路归并排序基数排序平均时间最坏情况辅助空间稳定性稳定稳定稳定稳定稳定不稳定不稳定 2不稳定排序举例 2,2,13,2,2,1(d=2，d=1) 2,2,1 2,1,1(大顶堆) O(n) O(n) O(n) O(n) O(n) O(n)O(n1.3222222O(n) O(n) O(n) O(n) O(n) O(n) O(n1.32222222O(1) O(1) O(n) O(1) O(1) O(1) O(1) ) 222) O(nlogO(nlogO(nlogn) n) n) O(n) O(log22n) 不稳定不稳定稳定稳定 O(nlogO(nlogn) n) O(1) O(n) O(d*(rd?n)) O(d*(rd?n)) O(rd) 2.若不考虑基数排序，则排序的两种基本操作是什么？解：关键字的比较和记录的移动。

3.外排序的基本操作是什么？解：生成有序归并段，归并。

4.分别采用堆排序、快速排序、起泡排序和归并排序，对初始状态为有序的表，则最省时间的是哪种排序方法？最费时间的是哪种排序方法？解：起泡排序，快速排序。

5.不受待排序初始序列的影响的排序算法是哪种？其时间复杂度是多少？解：简单选择排序，时间复杂度是O(n)。

6.直接插入排序设置监视哨的作用是什么？解：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。

7.从平均时间性能而言，哪种排序方法最佳？解：快速排序。

8.设待排序的记录有10个，其关键字分别为{75，23，98，44，57，12，29，64，38，82}。

手工执行以下排序算法(按字典序比较关键字的大小)，写出每一堂排序结束时的关键字的状态：(1)直接插入排序 (2)折半插入排序12第9章排序(3)起泡排序 (4)简单选择排序 (5)快速排序 (6)希尔排序 (7)2-路归并排序 (8)基数排序解：略9.已知记录序列R[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组C[1..n]，对每个记录R[i]，统计序列中关键字比它小的记录个数存于C[i]，则C[i]=0的记录必为关键字最小的记录，然后依C[i]值的大小对R中记录进行重新排列，试编写实现上述排序的算法。

第9章排序自测卷姓名班级一、填空题（每空1分，共24分）1. 大多数排序算法都有两个基本的操作：比较和交换。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。

3. 在插入和选择排序中，若初始数据基本正序，则选用插入排序；若初始数据基本反序，则选用选择排序。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用快速排序；若初始记录基本无序，则最好选用堆排序。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。

若对其进行快速排序，在最坏的情况下所需要的时间是。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。

7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍），共计移动次记录。

8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；二路归并排序一趟扫描的结果是；快速排序一趟扫描的结果是；堆排序初始建堆的结果是。

9. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取方法，其次选取方法，最后选取方法；若只从排序结果的稳定性考虑，则应选取方法；若只从平均情况下最快考虑，则应选取方法；若只从最坏情况下最快并且要节省内存考虑，则应选取方法。

二、单项选择题（每小题1分，共18分）（ B ）1．将5个不同的数据进行排序，至多需要比较9 次。

Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25（ C ）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序（ D ）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序（ B ）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。