归纳总结
## 归纳总结
下面对本章所介绍的排序算法进行一次系统的比较与复习。
1. 基本排序算法：适用于元素个数 $n$ 不是很大（$n < 10000$）的情形。
直接插入排序、冒泡排序和简单选择排序均属于此类，平均时间复杂度均为 $O(n^{2})$，实现简单。直接插入排序在小规模数据（$n \leqslant 25$）时效率较高；在最好情况下，仅需 $n - 1$ 次比较。冒泡排序在最好情况下只需 1 趟扫描和 $n - 1$ 次比较。简单选择排序的比较次数恒为 $O(n^{2})$，与初始排列无关，但移动次数受初始状态影响，最多不超过 $3(n - 1)$ 次。这三类算法的空间复杂度均为 $O(1)$，仅需一个辅助变量。其中，直接插入排序和冒泡排序是稳定的，而简单选择排序不稳定。
2. 对于中等规模数据（$n \leqslant 1000$），希尔排序是一种很好的选择。
它通过逐步缩小增量对子序列进行插入排序，初期移动距离大，后期接近有序，从而显著减
<!-- page: 403 -->
第8章 排序
391
少总的比较与移动次数。希尔排序代码简洁，空间开销小（开销为 $O(1)$），但属于不稳定排序。
3. 大规模高效排序算法：当 $n$ 很大时，应选用时间复杂度为 $O(n \log_2 n)$ 的算法。
快速排序是最通用的高效内部排序方法，平均时间复杂度为 $O(n \log_2 n)$，平均空间复杂度为 $O(\log_2 n)$，虽然在最坏情况下（如输入已有序）退化为 $O(n^2)$，但可通过“三者取中”等策略有效规避。堆排序的时间复杂度稳定为 $O(n \log_2 n)$，无性能退化问题，且仅需 $O(1)$ 的额外空间，但平均性能通常略逊于快速排序。归并排序的时间复杂度始终为 $O(n \log_2 n)$，与输入无关，稳定性好，但需要 $O(n)$ 的额外存储空间。基数排序具有线性时间复杂度 $O(d(n + r))$，但其实际效率受限于关键字结构和平台支持，通用性较弱，应用不如比较类排序广泛。
4. 混合策略：
实际系统常结合多种算法以扬长避短。例如，在归并排序或快速排序的递归底层切换为直接插入排序，可减少函数调用开销并提升局部效率。
综上，排序算法的选择应综合考虑数据规模、内存限制、稳定性要求及输入特性。深入理解各类算法的优劣，有助于在实际应用中做出更合理、高效的决策。
思维拓展
一道看似吓人的题目：对 $n$ 个整数进行排序，要求时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。
提示
设待排序整数的范围为 $0 - 65535$，设定一个数组int count[65535]并初始化为0，则所需空间与 $n$ 无关，为 $O(1)$。扫描一遍待排序列X[]，count[X[i]]++，时间复杂度为 $O(n)$；再扫描一次count[],当count[i]>0时，输出count[i]个i，排序完毕所需的时间复杂度也为 $O(n)$；所以总时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。另外，读者可能会问假如有负整数怎么办，这种情况下可以给所有整数都加上一个偏移量，使之都变成正整数，再使用上述方法。
购买王道书，就上
王道官方考研书店
wangdao.taobao.com
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 404 --> # 参考文献 [1] 严蔚敏，吴伟民．数据结构（C语言版）[M]．北京：清华大学出版社，2018． [2] 科尔曼，雷瑟尔森，李维斯特，等．算法导论[M]．3版．股建平，徐云，刘晓光，等译．北京：机械工业出版社，2013． [3] 李春葆，陈良臣，尹为民，等．数据结构教程（C++语言描述）[M]．北京：清华大学出版社，2009． [4] 陈守孔，胡潇琨，李玲．算法与数据结构考研试题精析[M]．北京：机械工业出版社，2007． [5] 夏清国．数据结构考研教案[M]．西安：西北工业大学出版社，2006． [6] 全国考研计算机大纲配套教材专家委员会．全国硕士研究生入学统一考试计算机专业基础综合考试大纲解析[M]．北京：高等教育出版社，2023． [7] 李春葆，尹为民，陈良臣．数据结构联考辅导教程[M]．北京：清华大学出版社，2010．