手撕十大排序算法（序章）
站长
· 阅读数 2
前言
十大排序包含：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序（快排）、桶排序、计数排序、基数排序以及堆排序。
十大排序可以分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
时间/空间复杂度
常见的时间/空间复杂度有：
- O（1）
- O（n）
- O（n2n^2n2）
- O（nlogn）
- O（nlog2log^2log2n）
- O（n+k）
- O（k）
十大排序算法的时间复杂度如下：
| 排序算法 | 平均时间复杂度 | 最优时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 是否原地排序 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O（n2n^2n2） | O（n） | O（n2n^2n2） | O（1） | 稳定 | 原地 |
| 选择排序 | O（n2n^2n2） | O（n2n^2n2） | O（n2n^2n2） | O（1） | 非稳定 | 原地 |
| 插入排序 | O（n2n^2n2） | O（n） | O（n2n^2n2） | O（1） | 稳定 | 原地 |
| 希尔排序 | O（nlogn） | O（nlog2log_2log2n） | O（nlog2log_2log2n） | O（1） | 不稳定 | 原地 |
| 归并排序 | O（nlogn） | O（nlogn） | O（nlogn） | O（n） | 稳定 | 非原地 |
| 快速排序 | O（nlogn） | O（nlogn） | O（n2n^2n2） | O（logn） | 不稳定 | 原地/非原地 |
| 桶排序 | O（n+k） | O（n+k） | O（n2n^2n2） | O（n+k） | 稳定 | 非原地 |
| 计数排序 | O（n+k） | O（n+k） | O（n+k） | O（k） | 稳定 | 非原地 |
| 基数排序 | O（n*k） | O（n*k） | O（n*k） | O（n+k） | 稳定 | 非原地 |
| 堆排序 | O（nlogn） | O（nlogn） | O（nlogn） | O（1） | 不稳定 | 原地 |
排序基础
1.时间复杂度、空间复杂度以及大O表示法，这里不再赘述
2.线性时间和非线性时间：线性时间可理解为线性函数，指数为1，比如O(n); 非线性时间可理解为非线性函数，指数不为1，比如O(n2)
3.稳定排序和非稳定排序：
- 3.1 稳定排序：当a=b，a在b之前，排序后a仍然在b之前
- 3.2 非稳定排序：当a=b，a在b之前，排序后a可能在b之后
4.原地排序和非原地排序：原地排序就是指不申请多余的空间来进行的排序，只在原来的排序数据中比较和交换。非原地排序则相反。