# 经典排序算法
十大经典排序算法
算法评定
- BigO - 大O符号
- 时间复杂度
- 对排序数据的总的操作次数，反映当 n 变化时，操作次数呈现什么规律
- 空间复杂度
- 指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数
- 稳定性
- 排序后两个相等键值的顺序和排序之前它们的顺序相同
# S. 开始
PS
- 非线性时间比较类
- 冒泡，选择，插入，希尔，归并，快速，堆排序
- 通过比较来决定元素相对次序，其时间复杂度不能突破 O(n log n)
- 线性时间非比较类
- 计数，桶，基数排序
- 不通过比较来决定元素相对次序，可以突破基于比较排序的时间下界，以线性时间运行
# A. 分析
- n：数据规模
- k：“桶”的个数
- In-place：占用常数内存，不占用额外内存
- Out-place：占用额外内存
时间复杂度
- 平方阶 (O(n^2)) 排序
- 冒泡排序，选择排序，插入排序
- 线性对数阶 (O(n log n)) 排序
- 归并排序，快速排序，堆排序
- O(n1 + §)) 排序，§ 是介于 0 和 1 之间的常数
- 希尔排序
- 线性阶 (O(n)) 排序
- 计数排序，桶（箱）排序，基数排序
参考