1.1排序算法的稳定性

排序算法的稳定性

稳定性:稳定排序算法会让原本有相等键值的记录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的记录R和S,且在原本的列表中R出现在S之前,在排序过的列表R也将时在S前面。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

当相等的元素是无法分辨的,比如像是整数,稳定性并不是一个问题。然而,假设以下的数对将要以他们的第一个数值来排序。

(4,1) (3,1) (3,7) (5,6)

在这个情况下,有可能产生两种不同的结果,一个是让相等键值的记录维持相对的次序,而另外一个则没有:

(3,1) (3,7) (4,1) (5,6)  (维持次序)
(3,7) (3,1) (4,1) (5,6)  (次序改变)

上述的次序改变情况就是属于不稳定情况

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄