数据结构基础之《（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()方法：
它会先做个反射，你让我排序的东西，是以值传递的还是以引用传递的
如果以值传递，直接快排
如果以引用排序，会用归并排序
考虑到稳固性
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。