第 8 章 排序

【考纲内容】

1.排序的基本概念；2. 直接插入排序；3. 折半插入排序；4. 起泡排序（Bubble Sort）；

5.简单选择排序；6. 希尔排序（Shell Sort）；7. 快速排序；8. 堆排序；

9.二路归并排序（Merge Sort）；10. 基数排序；11. 外部排序；12. 排序算法的分析和应用

【考情统计】

年份	题数及分值			考点
	单选题	综合题	总分值
2009	2	0	4	选择排序、排序算法的分析和应用
2010	2	0	4	交换排序、排序算法的分析和应用
2011	2	0	4	交换排序、选择排序
2012	2	0	4	插入排序、排序算法的分析和应用
2013	1	0	2	基数排序
2014	2	0	4	插入排序、交换排序
2015	2	0	4	插入排序、交换排序
2016	1	1	17	外部排序、快速排序的分治思想
2017	2	0	4	排序算法的分析和应用
2018	2	0	4	插入排序、选择排序
2019	3	0	6	交换排序、排序算法的分析和应用、外部排序
2020	2	0	4	选择排序、排序算法的分析和应用
2021	2	1	12	选择排序、基数排序
2022	2	1	12	归并排序、堆排序
2023	2	1	14	外部排序、排序算法的分析和应用、快速排序
2024	4	0	8	快速排序、大根堆、二路归并排序、败者树

【考点解读】
本章内容在 408 考试中主要以选择题的形式出现，但也考过几次应用题。虽然 408 考试还未在本章考过算法题，但未来也是有可能考的，不可忽视。各类排序算法的算法思想及各类排序算法的手工模拟是本章的重点，必须熟练掌握。408 考试也会着重考查各类排序算法的步骤和特点，以及它们之间的对比。
另外，提醒考生注意：408 考试是抽查，只要在 408 考试大纲范围内内容，408 考试都有可能考。例如，在 2023 年 408 考试中，命题人出其不意的考了一道 10 分的外部排序的应用题。外部排序这个知识点很多考生忽略了，甚至没有复习。导致这题的失分非常严重，一下子 10 分就没有了。数据结构这个科目在 408 考试中总共就 45 分，在这么一个细微的知识点上就丢失了10÷45≈22%的分数，这是非常可惜的！其实，只要记住了外部排序的过程，这题是很简单的。

【复习建议】
本章内容较为零散，由一个个独立的排序算法组成，各个算法之间其实关联性不强。考生可以利用碎片化的时间学习本章内容。学习本章时应注重动手模拟算法执行过程，结合具体的算法代码，深刻理解各种排序算法的具体步骤和特点。考生在复习过程中应注意以下几点：

      1.熟练掌握各种排序算法的步骤和特点，要能手写每一种排序算法的代码（应对算法题）。

        2.能够分析每一种算法的时间复杂度、空间复杂度及稳定性。

        3.熟练掌握各种排序算法的区别及其应用场景。

        4.了解外部排序的基本概念和步骤。

        如今 408 统考是大势所趋，408 考试难度越来越大。对于本章每一个排序算法的代码，建议考生都可以熟练写出，会分析各种排序算法的时间复杂度。

        最后，推荐一个学习本章内容的小技巧：因为真题常考各种排序算法的手工模拟，学完本章之后，建议大家在桌子上用便利贴写下一组数据，然后在每天开始复习之前花几分钟的时间，使用几个不同的排序方法对该组数据进行手动模拟排序并默写排序算法代码。坚持一段时间之后，大家就会对各种排序算法会有更加深刻的印象。

8.1 排序的基本概念

8.2 插入类排序

8.2.1 直接插入排序

8.2.2 折半插入排序

8.2.3 希尔排序

8.2.4 习题精编

8.2.5 真题演练

8.3 交换类排序

8.3.1 冒泡排序

8.3.2 快速排序

8.3.3 习题精编

8.3.4 真题演练

8.4 选择类排序

8.4.1 简单选择排序

8.4.2 堆排序

8.4.3 习题精编

8.4.4 真题演练

8.5 二路归并排序和基数排序

8.5.1 归并排序

8.5.2 基数排序

8.5.3 习题精编

8.5.4 真题演练

8.6 各种内部排序算法总结

8.6.1 内部排序算法对比

8.6.2 内部排序算法按特点分类

8.6.3 习题精编

8.6.4 真题演练

8.7 外部排序

8.7.1 外部排序的基本方法

8.7.2 多路平衡归并与败者树

8.7.3 置换-选择排序

8.7.4 最佳归并树

8.7.5 习题精编

8.7.6 真题演练

8.8 本章总结