算法稳定性和不稳定性区别，用意

Question

老师，算法的稳定性 和 不稳定性 不太理解，网上的答案也讲的不清晰，能否讲一下 稳定和不稳定的区别和用意，是否稳定对使用的场景有没有联系呢？

Answer 1

liuyubobobo 2019-02-24 15:14:04

课程在4-7小节会简单介绍稳定性的。（4：00开始）

稳定性不是算法的性质，而是专门针对“排序算法”的一种性质。指对于排序过程中，拥有相同的“比较值”的元素，在排序后，是否能保持原来的顺序。这个性质对于待排序的内容只是单独的元素并没有意义，但是对于待排序的内容是组合元素是有一定意义的。

比如，我们对一组学生数据按照分数进行排序。学生顺序原本是按照姓名排好了序，那么对于你的排序算法，能否做到按照分数排序后，对于相同分数的学生，依旧是按照姓名排序呢？

有的排序算法可以做到这一点（回忆上面我说的，所谓的：拥有相同的“比较值”的元素（分数），在排序后，能保持原来的顺序（姓名序）），这种排序算法就叫做稳定的；

有的排序不能做到这一点，这种排序算法就叫做不稳定的。

但其实，在现代计算机中，这个性质的意义并不大，因为我们总能够通过改变排序的比较方式（即定义两个元素的序是怎样的），来实现稳定排序，把本身不稳定的排序改稳定。

比如，在我上面的例子中，我们只需要定义，两个学生类，如果分数不同，分数小的靠前；否则，姓名小的靠前。就好了。我们只需要加一个”否则“，就能实现我们希望的”稳定“。这个算法会多判断一点，但是在现代计算机中，这一点判断微不足道。所以，至少在我接触的应用范畴里，除了考试和面试，基本用不上稳定性的。可能嵌入式相关的一些领域，对于这”一点多余的判断“会敏感吧：）

继续加油！：）

• 提问者 Woods #1

  感谢老师的解答