【文件属性】:
文件名称:leetcode中国-algorithm:多数算法没有考虑输入非法的情况
文件大小:149KB
文件格式:ZIP
更新时间:2021-06-29 20:25:00
系统开源
leetcode中国
基本排序算法
基于比较的排序
冒泡排序
没什么可说的,
改进方法就是加一个标志位防止有序后重复遍历.
由于需要遍历两次,
所以时间复杂度O(N^2)
传送门
-->
选择排序
外层从0开始默认outer是最小数的下标,
内存从outer+1位置开始遍历,
不稳定,
如{
3,
3,
3,
2
},
当比较最后一个4时,
是第一个3和2交换,
从而不稳定.
内外层遍历两次,
时间复杂度O(N^2)
传送门
-->
插入排序
相当于打扑克排序,
outer从1到N-1,
inner从outer到N-1,
时间复杂度O(N^2)
插入排序选择排序冒泡排序有浪费许多比较的次数
归并排序快的是因为小范围合并为大范围时,
有序可以同过外排方式
小组和为大组时,
组内有序没有浪费,
永远是组与组之间的比较
传送门
-->
希尔排序
迄今为止,
除了在一些特殊的情况下,
还没人能够从理论上分析希尔排序的效率,
有各种各样基于实验的评估,
估计它的时间级从O(N^(3/2))到O(N^(7/6))
传送门
-->
归并排序
递归把一个数字分隔为两部分,
T(N)
=
2*T(N/2