[项目014] 排序的综合应用 隐藏答案 | 返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。

最后更新：2023年12月24日

---

【课后作业】

作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。

1. 设待排序的关键字序列为 {12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}，试分别写出使用以下排序方法对关键字进行从小到大排序的过程，每趟排序结束后关键字序列的状态。（1）直接插入排序；（2）折半插入排序；（3）希尔排序（增量选取5、3、1）；（4）冒泡排序；（5）快速排序；（6）简单选择排序；（7）堆排序；（8）二路归并排序。

答案及解析：
（1）直接插入排序；
初 始：(12), 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟：(2, 12), 16, 30, 28, 10, 16*, 20, 6, 18
第2趟：(2, 12, 16), 30, 28, 10, 16*, 20, 6, 18
第3趟：(2, 12, 16, 30), 28, 10, 16*, 20, 6, 18
第4趟：(2, 12, 16, 28, 30), 10, 16*, 20, 6, 18
第5趟：(2, 10, 12, 16, 28, 30), 16*, 20, 6, 18
第6趟：(2, 10, 12, 16, 16*, 28, 30), 20, 6, 18
第7趟：(2, 10, 12, 16, 16*, 20, 28, 30), 6, 18
第8趟：(2, 6, 10, 12, 16, 16*, 20, 28, 30), 18
第9趟：(2, 6, 10, 12, 16, 16*, 18, 20, 28, 30)

（2）折半插入排序
折半插入排序与直接插入排序每趟生成的序列完全相同，区别只是在对比元素时使用折半查找，比直接插入排序所使用的顺序查找速度更快。

（3）希尔排序（增量选取5、3、1）
初 始：12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟（增量5）：10, 2, 16, 6, 18, 12, 16*, 20, 30, 28
第2趟（增量3）：6, 2, 12, 10, 18, 16, 16*, 20, 30, 28
第3趟（增量1）：2, 6, 10, 12, 16, 16*, 18, 20, 28, 30

（4）冒泡排序
初 始： 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟： 2, 12, 16, 28, 10, 16*, 20, 6, 18, (30)
第2趟： 2, 12, 16, 10, 16*, 20, 6, 18, (28, 30)
第3趟： 2, 12, 10, 16, 16*, 6, 18, (20, 28, 30)
第4趟： 2, 10, 12, 16, 6, 16*, (18, 20, 28, 30)
第5趟： 2, 10, 12, 6, 16, (16*, 18, 20, 28, 30)
第6趟： 2, 10, 6, 12, (16, 16*, 18, 20, 28, 30)
第7趟： 2, 6, 10, (12, 16, 16*, 18, 20, 28, 30)
第8趟： 2, 6, (10, 12, 16, 16*, 18, 20, 28, 30)
第9趟： 2, (6, 10, 12, 16, 16*, 18, 20, 28, 30)
第10趟：(2, 6, 10, 12, 16, 16*, 18, 20, 28, 30)

（5）快速排序
初 始：12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟：6, 2, 10, (12), 28, 30, 16*, 20, 16, 18
第2趟：(2, 6, 10), (12), 28, 30, 16*, 20, 16, 18
第3趟：(2, 6, 10, 12), 18, 16, 16*, 20, (28, 30)
第4趟：(2, 6, 10, 12), 16*, 16, (18, 20, 28, 30)
第5趟：(2, 6, 10, 12), (16*, 16), (18, 20, 28, 30)

（6）简单选择排序
初 始： () 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟： (2), 12, 16, 30, 28, 10, 16*, 20, 6, 18
第2趟： (2, 6), 16, 30, 28, 10, 16*, 20, 12, 18
第3趟： (2, 6, 10), 30, 28, 16, 16*, 20, 12, 18
第4趟： (2, 6, 10, 12), 28, 16, 16*, 20, 30, 18
第5趟： (2, 6, 10, 12, 16), 28, 16*, 20, 30, 18
第6趟： (2, 6, 10, 12, 16, 16*), 28, 20, 30, 18
第7趟： (2, 6, 10, 12, 16, 16*, 18), 20, 30, 28
第8趟： (2, 6, 10, 12, 16, 16*, 18, 20), 30, 28
第9趟： (2, 6, 10, 12, 16, 16*, 18, 20, 28), 30
第10趟：(2, 6, 10, 12, 16, 16*, 18, 20, 28, 30)

（7）堆排序
堆排序有两种方法，方法一是直接构建一个小根堆，然后输出小根堆的堆顶元素，之后再对堆进行调整后，继续输出堆顶元素，直至输出完毕；方法二是先构建一个大根堆，然后依次将堆顶元素和最后一个元素进行交换，并将其置为确定元素，其余元素继续按照大根堆构建方法进行调整。

方法一：
a. 将序号按照完全二叉树的顺序进行排列
🏷️Img_Pro1410

b. 创建一个小根堆
🏷️Img_Pro1410A1

c. 排序过程
🏷️Img_Pro1410A2

方法二:
a. 将序号按照完全二叉树的顺序进行排列
🏷️Img_Pro1410

b. 创建一个大根堆
🏷️Img_Pro1410B1

c. 排序过程B
🏷️Img_Pro1410B2

（8）二路归并排序
初 始：12, 2, 16, 30, 28, 10, 16*, 20, 6, 18
第1趟：(2, 12), (16, 30), (10, 28), (16*, 20), (6, 18)（归并长度为2）
第2趟：(2, 12, 16, 30), (10, 16*, 20, 28), (6, 18) （归并长度为4）
第3趟：(2, 10, 12, 16, 16*, 20, 28, 30), (6, 18) （归并长度为8）
第4趟：(2, 6, 10, 12, 16, 16*, 18, 20, 28, 30) （归并长度为10）

【拓展练习】

1. 给出关键字序列 {4, 5, 1, 2, 6, 3} 的直接插入排序过程。

答案及解析：
直接插入排序过程如下。
初 始：(4), 5, 1, 2, 6, 3
第1趟：(4, 5), 1, 2, 6, 3 (插入5)
第2趟：(1, 4, 5), 2, 6, 3 (插入1)
第3趟：(1, 2, 4, 5), 6, 3 (插入2)
第4趟：(1, 2, 4, 5, 6), 3 (插入6)
第5趟：(1, 2, 3, 4, 5, 6) (插入3)

2. 给出关键字序列 {50, 26, 38, 80, 70, 90, 8, 30, 40, 20} 的希尔排序过程（取增量序列为 d = {5, 3, 1}，排序结果为从小到大排列）。

答案及解析：

原始序列：50, 26, 38, 80, 70, 90, 8, 30, 40, 20
第一趟(增量5)：50, 8, 30, 40, 20, 90, 26, 38, 80, 70
第二趟(增量3)：26, 8, 30, 40, 20, 80, 50, 38, 90, 70
第三趟(增量1)：8, 20, 26, 30, 38, 40, 50, 70, 80, 90

3. 已知序列 {503, 87, 512, 61, 908, 170, 897, 275, 653, 462}，采用2路归并排序法对该序列做升序排序时需要几趟排序？给出每一趟的结果。

答案及解析：
当n=10时，需要排序的趟数 $= \lceil log_2 10 \rceil = 4$，各趟的排序结果如下：
初 始：503, 87, 512, 61, 908, 170, 897, 275, 653, 462
第1趟：(87, 503), (61, 512), (170, 908), (275, 897), (462, 653) （归并长度为2）
第2趟：(61, 87, 503, 512), (170, 275, 897, 908), (462, 653) （归并长度为4）
第3趟：(61, 87, 170, 275, 503, 512, 897, 908), (462, 653) （归并长度为8）
第4趟: (61, 87, 170, 275, 462, 503, 512, 653, 897, 908) （归并长度为10）

4. 设待排序的排序码序列为 {12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}，试写出使用基数排序方法每趟排序后的结果，并说明做了多少次排序码比较。

答案及解析：
原始序列：12, 2, 16, 30, 28, 10, 16*, 20, 6, 18

第1趟分配个位：

0	1	2	3	4	5	6	7	8	9
30	↑	12	↑	↑	↑	16	↑	28	↑
10	↑	2	↑	↑	↑	16*	↑	18	↑
20	↑	↑	↑	↑	↑	6	↑	↑	↑

第1趟收集：30, 10, 20, 12, 2, 16, 16*, 6, 28, 18

第2趟分配十位：

0	1	2	3	4	5	6	7	8	9
2	10	20	30	↑	↑	↑	↑	↑	↑
6	12	28	↑	↑	↑	↑	↑	↑	↑
↑	16	↑	↑	↑	↑	↑	↑	↑	↑
↑	16*	↑	↑	↑	↑	↑	↑	↑	↑
↑	18	↑	↑	↑	↑	↑	↑	↑	↑

第2趟收集：2, 6, 10, 12, 16, 16*, 18, 20, 28, 30