冒泡排序与排序的稳定性|Bubble Sort and Stability

第一期选择排序： https://wznmickey.com/2020/selection-sort/

视频版：
Bilibili: https://www.bilibili.com/video/BV1Dt4y1U7SR/

文字版：
水中气泡有大有小，
上升速度也有快有慢，
比较相邻的2个气泡，
就可以明白哪个先到水面。
同样的，
我们也可以比较相邻的2个数字，
从而排序。
大家好，这里是静谈算法，
我是静静。
你在看的是排序算法的第二期，冒泡排序与排序的稳定性。

考虑这样一个情况，五位同学的分数分别为
37、39、34、65、65，
如何对他们从高分到低分进行排名呢？
首先比较第一个数和第二个数，
37小于39，于是交换，
变为39、37、34、65、65，
之后第二个数和第三个数进行比较，顺序不变
接着是第三个数和第四个数，
变为39、37、65、34、65，
最后是34和65进行比较
再次交换，变为39、37、65、65、34。
此时最后的34就是所有数中的最小值。
接下来同样操作，
第一个数与第二个数比较，不变。
第二个数和第三个数比较，交换。
变为39、65、37、65、34。
第三个数和第四个数比较，交换。
变为39、65、65、37、34。
由于第五个数34已经是之前已得出的最小数，
所以第四个数37不用和第五个数比较，为次小值。
接下来在前3个数中找最小值。
同上，第一个数与第二个数比较，交换，
变为65、39、65、37、34。
之后，第二个数和第三个数比较，交换，
变为65、65、39、37、34。
此时末三位的顺序已经确定，
只需要确定第一位与第二位即可。
观察后发现，均为65，
看起来交换与否都一样。
但是还记得开始的情况是什么吗？
对，我们要对学生成绩进行排序，
同样的成绩对应着不同的人，
我们可以用学号区分这5位同学，
不妨设为1号、2号、3号、4号、5号。
此时的2位65分的学生为4号和5号，
出于减少步骤的原则，
当分数相等时，
我们不进行交换。
此时我们会发现，
一开始4号在5号前面，
排序完后4号仍在5号前面，
同分的学生之间的相对顺序没有发生改变。
这就是排序的稳定性。
当然，并不是所有的排序算法都满足这一特性，
下期介绍一种快得多的但没有稳定性的算法。
想看的朋友不要忘记点赞加关注，
也欢迎访问我的博客静静的小窝看更多内容。
这里是静谈算法，我是静静，
我们下期见。