键相等时,原次序仍有意义

两条记录的排序键相同,其他内容却可能不同。按城市处理交易时,若输入已经按到达时间排列,稳定排序能把同城交易聚到一起,同时保留城内原有先后次序;不稳定排序仍可能把城市排对,却打乱这层次序。

相等依据的是本次排序采用的键或比较规则,而不是要求整条记录完全一样。只比较姓名时,同名但年龄不同的两条记录属于同键;若比较规则又加入年龄,它们可能不再相等,稳定性承诺所作用的范围也随之改变。

参考:[1] [2]

多字段可按次要到主要依次排

稳定性支持分多轮建立复杂次序。要以年级为主要键、年龄为次要键,可以先按年龄排,再稳定地按年级排;第二轮把同年级内容聚合时,不破坏其中已经形成的年龄顺序。若先排主要键再排次要键,通常会改变想要的优先级。

也可以构造同时包含多个字段的复合键,直接按它们的字典式优先级比较。稳定排序特别有用的场合,是当前步骤只负责一个新键,而希望继承原输入已有、且未完全写进比较器的次序。

参考:[2]

稳定性来自具体移动规则

插入排序只越过严格较大键、归并相等时优先取左项,都是维持稳定性的具体做法。普通选择排序的远距离交换、堆排序或快速排序的常见交换安排,则可能让同键记录互相越过;同一算法家族也能有另作设计的稳定变体。

把原始位置作为最后一个比较字段,可以为同键记录显式建立原次序,但需要保存并正确使用这个位置。稳定性仍不保证上游输入次序本身有业务意义,也不能修复不自洽的比较规则;这些前提应与排序算法分别检查。

参考:[1] [2]