数据结构基础之《（15）—排序算法小结》

一、排序算法的稳定性

1、稳定性是指同样大小的样本再排序之后不会改变相对次序

2、对基础类型来说，稳定性毫无意义
比如：3和3没有区别。《潜伏》里说同样两个一百元大钞，你能告诉我哪一个是高尚的那一个是龌龊的么

3、对非基础类型来说，稳定性有重要意义
比如：有很多个学生，学生有班级号和年龄
第一回按年龄从小到大排序
得到一个序列，年龄是从小到大的
基于这个序列，再按照班级号从小到大排序
排完之后，如果排序有稳定性的，在1班的学生内部，年龄是从小到大排序的

4、有些排序算法可以实现成稳定的，而有些排序算法无论如何都实现不成稳定的

5、什么算法是稳定的，什么算法是不稳定的
（1）选择排序
没有稳定性，因为它是从0到n-1中找最小值，然后交换
例子：
[5 5 5 5 5 5 1 5 5 5 5]
第一个5和1交换，第一个5会跑到后面几个5的后面，原序列中两个5的相对前后顺序就被破坏了

（2）冒泡排序
有稳定性
处理相等时的态度，就决定了它稳定性能不能实现
相等时不交换，稳定性不会破坏

（3）插入排序
有稳定性

（4）归并排序
有稳定性

（5）快速排序
没有稳定性

（6）堆排序
没有稳定性，因为堆结构根本不考虑稳定不稳定

二、小结

1、排序算法总结

	时间复杂度	额外空间复杂度	稳定性
选择排序	O(N^2)	O(1)	无
冒泡排序	O(N^2)	O(1)	有
插入排序	O(N^2)	O(1)	有
归并排序	O(N*logN)	O(N)	有
随机快排	O(N*logN)	O(logN)	无
堆排序	O(N*logN)	O(1)	无
计数排序	O(N)	O(M)	有
基数排序	O(N)	O(N)	有

（1）不基于比较的排序，对样本数据有严格要求，不易改写
（2）基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
（3）基于比较的排序，时间复杂度的极限是O(N*logN)
（4）时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的
（5）为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并

2、常见的坑
（1）归并排序的额外空间复杂度可以变成O(1)，“归并排序 内部缓存法”，但是将变得不再稳定
没必要，直接用堆排序
（2）“原地归并排序”是垃圾，会让时间复杂度变成O(N^2)
没必要，直接用插入排序
（3）快速排序稳定性改进，“01 stable sort”，但是会对样本数据要求更多
没必要，论文里的，限制条件很多

3、工程上对排序的改进
（1）稳定性的考虑
（2）充分利用O(N*logN)和O(N^2)排序各自的优势

例如Java中Arrays.sort()方法：
它会先做个反射，你让我排序的东西，是以值传递的还是以引用传递的
如果以值传递，直接快排
如果以引用排序，会用归并排序
考虑到稳定性