排序前两个相等的数 在序列中的前后位置顺序 和排序后它们两个的前后位置相同.
如原序列中r[i]=r[j], 且r[i]在r[j]之前, 而在排序后的序列中, r[i]仍在r[j]之前,
则称这种排序算法是稳定的, 否则称为不稳定的.
# O(N^2)的排序
1. 冒泡排序(稳定)
冒泡排序是比较相邻两个元素, 元素相等的话顺序不作交换, 因此稳定.
2. 插入排序(稳定)
插入排序是在已有的有序序列基础上, 每次插入新的元素, 如果相等的话, 新元素放在相等元素的后面,
所以相等元素顺序没有发生改变, 因此稳定.
3. 选择排序(不稳定)
反例: [5, 8, 5, 2, 9] , 第一次循环会把0下标和3下标交换, 原序列的5前后位置发生了改变, 因此不稳定.
# O(NlogN)的排序
1. 归并排序(稳定)
归并排序只要在merge左右序列的时候, 如果左右序列对应元素相等时, 先拷贝左序列元素, 即可做到稳定性.
2. 快排(不稳定)
不作证明, 记住结论.
3. 堆排序(不稳定)
反例: [4, 4, 4, 5, 5] , 在构建大根堆的时候已经破坏了稳定性.
如果要排序的内容原本的初始顺序存在意义, 那么需要稳定性的算法, 使得在二次排序的基础上保持原有的排序,
如果不需要保持初始的排序意义, 那么使用稳定性算法将毫无意义.
例如: 排序的内容是一组按照价格高低排序的对象, 如今需要按照销量高低排序, 使用稳定性算法,
可以使相同销量的对象依然保持价格高低的排序, 只有销量不同的才会重新排序.