排序问题与稳定性
复习
- 算法与正确性：算法既要正确，也要能终止
- 大 O 记号：用增长量级衡量算法
- 数组：连续存储，可按下标交换元素
TL;DR
- 排序把数据按某种顺序排列
- 排序常为后续的查找、去重和统计做准备
- “稳定性”指相等元素的原顺序是否被保留
- 不同排序算法在时间、空间、稳定性上各有取舍
正文
接下来一整组章节，都围绕一个极其常见的问题：排序——把一堆数据按某种顺序排好。
为什么要排序
排序本身看似没什么产出，但它常常是别的事情的“垫脚石”：
- 便于查找：有序之后，就能用二分查找，把
O(n)变成O(log n) - 便于去重：相同的元素排在一起，一眼就能看出重复
- 便于统计与展示：按大小、时间、名字排列，符合人的阅读习惯
所以，排序是很多算法的前置步骤。先花点时间整理顺序，往往能省下后面大量的时间。
什么叫“稳定”
排序还有一个容易被忽略、却很关键的属性：稳定性（stability）。
它说的是：如果两个元素大小相等，排序后，它们原本的先后顺序是否保持不变。
- 稳定：相等元素的相对顺序保留
- 不稳定：相等元素的相对顺序可能被打乱
什么时候需要稳定？举个例子：先把学生按成绩排序，再想“成绩相同时按姓名排”。如果第二次排序是稳定的，那成绩相同的那些人里，之前按姓名排好的顺序就会被保留。“稳定”让多次排序可以层层叠加，而不会把之前的成果打乱。
还要看什么
评价一个排序算法，通常要综合几方面：
- 时间：最好、最坏、平均各是多少
- 空间：是否需要额外的存储
- 稳定性：相等元素顺序是否保留
没有哪个排序算法样样都好。接下来几章，我们会认识好几种，看看它们各自的特点，以及在什么场景下更合适。
思考题 1
为什么排序有助于后续的查找和去重？
思考题 2
排序的“稳定性”指什么？它在什么情况下重要？
小结
知识点
- 排序把数据按某种顺序排列
- 排序为查找、去重、统计提供便利
- 稳定性指相等元素的原顺序是否保留
- 评价排序要看时间、空间与稳定性
参考资料
- Wikipedia(zh)：排序算法：把数据按序排列的算法
- Wikipedia(zh)：排序算法的稳定性：相等元素顺序是否保留的性质
思考题答案（仅供参考）
思考题 1
因为有序之后，查找可以借助二分把代价降到 O(log n)；相同的元素也会相邻排列，容易识别和合并，去重因此变得简单。排序相当于为这些操作预先铺好了路。
思考题 2
稳定性指排序后，大小相等的元素是否保持原来的相对顺序。当需要多次按不同字段排序、并要求后续排序不打乱之前结果时，稳定性就很重要。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪