搭建一个网站要多久,企业网站建设费用怎么记账,深圳营销型网站设计,旅行社网站开发 论文一、排序算法的稳定性
1、稳定性是指同样大小的样本再排序之后不会改变相对次序
2、对基础类型来说#xff0c;稳定性毫无意义 比如#xff1a;3和3没有区别。《潜伏》里说同样两个一百元大钞#xff0c;你能告诉我哪一个是高尚的那一个是龌龊的么
3、对非基础类型来说稳定性毫无意义 比如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()方法 它会先做个反射你让我排序的东西是以值传递的还是以引用传递的 如果以值传递直接快排 如果以引用排序会用归并排序 考虑到稳定性
