2024年6月2日发(作者：虎谷芹)
第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
均不大于其左右两个分支
结点的关键字值k
2
和k
2i+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的任意文件进行排序，则至少需进行nlog
2
n次比较。
9. 试构造对5个整数元素进行排序，最多只用7次比较的算法思想。
10. 有n个不同的英文单词，它们的长度相等，均为m，如果n≥50，且m<5，试问
采用什么排序方法时间复杂度最佳？为什么？
11. 如果只想得到一个序列中第k个最小元素的部分排序序列，最好采用什么排序方
法？为什么？如果有这样一个序列：( 57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7 )，得到其
第4个最小元素之前的部分序列 ( 6, 7, 9, 11 )，使用所选择的算法实现时，要执行多少次
比较？
12. 对于快速排序的非递归算法，可以用队列（而不用栈）实现吗？如果能，试说明
理由；如果不能？也要说明理由。
二、填空题
1. 在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。
2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好
选用 排序法。
3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法使是 。
4. 一组记录的关键字为 ( 46, 79, 56, 38, 40, 84 )，则利用堆排序的方法建立的初始堆
为 。
5. 一组记录的关键字为 ( 46, 79, 56, 38, 40, 84 )，则利用快速排序的方法，以第1个记
录为基准得到的一次划分结果为 。
6. 排序方法中，从未排序序列中依次取出元素，与已排序序列（初始为空）中的元素
进行比较，将其放入已排序序列的正确位置上的方法，称为 。
7. 排序方法中，从未排序序列中依次取出元素，并将其依次放入已排序序列（初始为
空）的一端的方法，称为 。
8. 用某种排序方法对线性表 ( 25, 84, 21, 47, 15, 27, 68, 35, 20 ) 进行排序，元素序列变
化情况如下：
(1) 25, 84, 21, 47, 15, 27, 68, 35, 20
(2) 20, 15, 21, 25, 47, 27, 68, 35, 84
(3) 15, 20, 21, 25, 35, 27, 47, 68, 84
(4) 15, 20, 21, 25, 27, 35, 47, 68, 84
则采用的排序方法是 。
9. 快速排序方法在 情况下最不利于发挥其长处。
10. 在插入排序、选择排序、快速排序及归并排序中， 方法要求内存量最大。
11. 在插入排序、选择排序、快速排序及归并排序中，平均查找长度最小的是 。
12. 在一组记录 ( 54, 38, 96, 23, 15, 72, 60, 45, 83 ) 进行直接插入排序中，当把第7个
记录60插入到有序表时，为寻找插入位置需要比较 次。
2024年6月2日发(作者：虎谷芹)
第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
均不大于其左右两个分支
结点的关键字值k
2
和k
2i+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的任意文件进行排序，则至少需进行nlog
2
n次比较。
9. 试构造对5个整数元素进行排序，最多只用7次比较的算法思想。
10. 有n个不同的英文单词，它们的长度相等，均为m，如果n≥50，且m<5，试问
采用什么排序方法时间复杂度最佳？为什么？
11. 如果只想得到一个序列中第k个最小元素的部分排序序列，最好采用什么排序方
法？为什么？如果有这样一个序列：( 57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7 )，得到其
第4个最小元素之前的部分序列 ( 6, 7, 9, 11 )，使用所选择的算法实现时，要执行多少次
比较？
12. 对于快速排序的非递归算法，可以用队列（而不用栈）实现吗？如果能，试说明
理由；如果不能？也要说明理由。
二、填空题
1. 在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。
2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好
选用 排序法。
3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法使是 。
4. 一组记录的关键字为 ( 46, 79, 56, 38, 40, 84 )，则利用堆排序的方法建立的初始堆
为 。
5. 一组记录的关键字为 ( 46, 79, 56, 38, 40, 84 )，则利用快速排序的方法，以第1个记
录为基准得到的一次划分结果为 。
6. 排序方法中，从未排序序列中依次取出元素，与已排序序列（初始为空）中的元素
进行比较，将其放入已排序序列的正确位置上的方法，称为 。
7. 排序方法中，从未排序序列中依次取出元素，并将其依次放入已排序序列（初始为
空）的一端的方法，称为 。
8. 用某种排序方法对线性表 ( 25, 84, 21, 47, 15, 27, 68, 35, 20 ) 进行排序，元素序列变
化情况如下：
(1) 25, 84, 21, 47, 15, 27, 68, 35, 20
(2) 20, 15, 21, 25, 47, 27, 68, 35, 84
(3) 15, 20, 21, 25, 35, 27, 47, 68, 84
(4) 15, 20, 21, 25, 27, 35, 47, 68, 84
则采用的排序方法是 。
9. 快速排序方法在 情况下最不利于发挥其长处。
10. 在插入排序、选择排序、快速排序及归并排序中， 方法要求内存量最大。
11. 在插入排序、选择排序、快速排序及归并排序中，平均查找长度最小的是 。
12. 在一组记录 ( 54, 38, 96, 23, 15, 72, 60, 45, 83 ) 进行直接插入排序中，当把第7个
记录60插入到有序表时，为寻找插入位置需要比较 次。