阅读 ‧ 电子书库

稳定排序

在排序函数cmp认为原始无序集合中的两个元素a_i和a_j是相等的时候，在有序结果集合中维护这两个元素之间的相对顺序也许是很重要的，也就是说，如果i＜j，那么a_i的最终位置必须在a_j的最终位置的左边。能够保证这种性质的排序算法都被认为是稳定的。例如，在图4-4的顶部表示了一个已经按照当天航班时间（忽略航线或者目的地这两个参数）排好序的航班信息集合A。如果A使用一个排序函数（cmpDestination）按照目的地来对航班进行排序，得到的一个可能结果如图4-4的底部所示。

你将注意到所有具有相同到达地点的航班按照既定离港时间排好序了，因此，这个排序算法是稳定的。一个不稳定的算法不会关注原始集合中的元素位置之间的关系（也许它会维护相对顺序，也许不会）。