十大排序算法 sort algorithm
2019-02-14 本文已影响11人
1江春水
算法分类
- 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(n*log n)，因此称为非线性时间比较类排序算法；
- 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较类排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序算法；
非线性比较类排序算法：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 归并排序
- 希尔排序
- 堆排序
线性时间非比较类排序算法：
- 计数排序
- 桶排序
- 基数排序
排序相关概念：
- 稳定：如果a原本在b前边，a=b，排序完后，a依旧在b前边；
- 不稳定：如果a原本在b前边，a=b，排序完后，b在a的前边；
- 时间复杂度：对排序数据总得操作次数，当n变化时，操作次数呈现什么规律；
- 空间复杂度：指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数；
关于时间复杂度：
- 平方阶 O(n^2) 排序
- 各类简单排序：直接插入、直接选择和冒泡排序。
- 线性对数阶 O(nlog2n) 排序:快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序 - 线性阶 O(n) 排序 基数排序，此外还有桶、箱排序。
复杂度图解：
sort.png
