如果我问你：排序算法的「稳定性」有何意义？你怎么回答？

虽然我们在工作不一定经常去写排序算法，但是排序算法却是充斥着我们的程序生活，比如你不经意间调用了SDK中的某个sort算法，其背后无非是什么快排、归并等算法。而且在我们面试的过程中也会经常被问及，如果你在面试的过程中连一个最基本的冒泡排序都不会写的话，那么很明显的面试结果也不会好到哪里去。

除了基本的实现之外，我们关注排序算法的同时，往往还会关注它的时间复杂度和空间复杂度。在面试之前，我们可能还会临时抱佛脚的去记一下其稳定性。下表中列举了几种常见的排序算法的核心总结。

对于时间复杂度和空间复杂度这种倒是好理解，如果你经常刷leetcode，就会非常关注此类问题。但是「稳定性」这个属性往往被我们所忽视，我们一般会记住稳定性的定义以及特定算法所对应的稳定性，但是是否想过「稳定性」有何意义？

稳定性的定义：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

如果我们只是面对简单的数字排序，那么稳定性确实也没有多大意义。比如，1 2 3 3 4的序列中如果第一个3和第二个3在sort方法反复执行之后位置也反复变化，但是对于调用sort方法所想要获得排序结果的上游应用而言，那么结果还是1 2 3 3 4，至于3的次序，无关紧要。

如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）

如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。

那么排序算法的「稳定性」在什么情况下才会变得有意义呢？

举个例子，一个班的学生已经按照学号大小排好序了，我现在要求按照年龄从小到大再排个序，如果年龄相同的，必须按照学号从小到大的顺序排列。那么问题来了，你选择的年龄排序方法如果是不稳定的，是不是排序完了后年龄相同的一组学生学号就乱了，你就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法，我就只需要按照年龄排一遍就好了。

从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法。

排序算法的「稳定性」有何意义？这个还是要分应用场景来看，很多使用情况下，并没有什么实质的意义，而在有些情况下却有很重要的意义。

有很多算法你现在看着没啥，但是当放在大数据云计算的条件下它的稳定性非常重要。举个例子来说，对淘宝网的商品进行排序，按照销量，价格等条件进行排序，它的数据服务器中的数据非常多，因此，当时用一个稳定性效果不好的排序算法，如堆排序、shell排序，当遇到最坏情形，会使得排序的效果非常差，严重影响服务器的性能，影响到用户的体验。

排序算法的「稳定性」有何意义？你以前是否忽略了这个问题，那么现在你Get到了吗？或者你有更好的答案，欢迎在文末留言。

想知道更多？扫描下面的二维码关注我