Chapter2: 查找与排序
8. 分析十种排序算法的稳定性
1. 什么是算法的稳定性
-
稳定
如果a=b, a原来在b前面, 排序之后a仍然在b前面
-
不稳定
如果a=b, a原来在b前面, 排序之后a可能在b之后
2. 十种排序算法的稳定性
-
堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法；
比如希尔排序，由于前面进行的是分组的插入排序，两个相等的值可能分再不同的组，进行插入排序后相对的前后位置可能会发生改变
选择排序是循环选择最小的数直接放在最前面，所以可能会将后面的相同的值直接调到前面(其实如果是从右往左扫描，只有在找到更大值才交换的话，相对位置也是不变的才对呀...(这个问题网上也有争议...)
-
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
比如冒泡排序，是比较温和的排序，有两两之间的比较，所以相对顺序不变
直接插入排序也是，最靠前的无序元素挨个跟前面的有序元素列表比较，找到
>=它的就插在后面，相对位置也是不变的
3. 参考资料
[1] 八大排序算法稳定性分析
