打开网站弹出qq对话框北京seo网站设计
一、排序算法的稳定性
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()方法：
它会先做个反射，你让我排序的东西，是以值传递的还是以引用传递的
如果以值传递，直接快排
如果以引用排序，会用归并排序
考虑到稳定性