排序

排序（Sorting）是按关键字把一组数据元素排成递增或递减次序的过程，也是计算机科学中最基础、应用最广泛的问题之一。数据库索引、搜索结果、成绩排名、快递分拣，背后都依赖高效的排序算法。

本章沿着插入、交换、选择、归并、基数这五大类算法展开，因为每一类的解题思路都不同：插入与选择一次只把有序前缀往前推一个元素，交换靠成对互换把元素各归其位，归并利用一段已经排好的数据，基数则按单个数位分桶而不去比较整个关键字。学习顺序大致可以分成三段：基础路线从插入排序到冒泡排序再到选择排序，先掌握 $O(n^2)$ 级的简单排序；进阶路线由快速排序、归并排序到堆排序，理解分治思想与堆结构；扩展路线则延伸到希尔排序、基数排序与外部排序，了解改进方法与非比较排序。

面对不同规模、不同初始状态的数据该选哪种算法，稳定性与空间开销又如何权衡，是本章要反复回答的问题。判断一个排序在实践中好不好用，离不开三个评价指标：时间复杂度、空间复杂度与稳定性，其中稳定性指的是相等元素在排序前后保持相对位置不变，算法有稳定与不稳定之分。为此，本章会系统介绍各类内部排序与外部排序算法，帮助你在实际应用中做出正确选择。读完本节，你能够写出每种排序算法的核心代码并分析其时间与空间复杂度，说明各种算法各自适合什么样的数据分布，也能根据具体数据集选定算法而不是凭印象随手挑一个，并且了解外部排序与多路归并的基本思想。