算法
算法概述
十种常见排序算法可以分为两大类：
非线性时间比较类排序： 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序： 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
算法复杂度
| 排序 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | 0(n^2) | 0(n^2) | 0(n) | 0(1) | 稳定 |
| 希尔排序 | 0(n^1.3) | 0(n^2) | 0(n) | 0(1) | 不稳定 |
| 选择排序 | 0(n^2) | 0(n^2) | 0(n^2) | 0(1) | 不稳定 |
| 堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | 0(1) | 不稳定 |
| 冒泡排序 | 0(n^2) | 0(n^2) | 0(n) | 0(1) | 稳定 |
| 快速排序 | O(nlog₂n) | 0(n^2) | O(nlog₂n) | O(nlog₂n) | 不稳定 |
| 归并排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | 0(n) | 稳定 |
| 计数排序 | 0(n+k) | 0(n+k) | 0(n+k) | 0(n+k) | 稳定 |
| 桶排序 | 0(n+k) | 0(n^2) | 0(n^2) | 0(n+k) | 稳定 |
| 基数排序 | 0(n+k) | 0(n+k) | 0(n*k) | 0(n+k) | 稳定 |
相关概念
稳定： 如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
不稳定： 如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度： 对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
空间复杂度： 是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。