常见排序算法的时间复杂度与空间复杂度总结
1. 冒泡排序（Bubble Sort）
- 时间复杂度：
- 最好：O(n)（数组已有序，加入标志位提前退出）
- 平均：O(n²)
- 最坏：O(n²)（数组逆序）
- 空间复杂度：O(1)（原地排序，仅需临时变量）
2. 选择排序（Selection Sort）
- 时间复杂度：
- 最好：O(n²)（需遍历所有元素找到最小/大值）
- 平均：O(n²)
- 最坏：O(n²)
- 空间复杂度：O(1)（原地排序，仅需临时变量）
3. 插入排序（Insertion Sort）
- 时间复杂度：
- 最好：O(n)（数组已有序，无需移动元素）
- 平均：O(n²)
- 最坏：O(n²)（数组逆序，每次插入需移动所有已排序元素）
- 空间复杂度：O(1)（原地排序，仅需临时变量）
4. 快速排序（Quick Sort）
- 时间复杂度：
- 最好：O(n log n)（每次均匀划分数组）
- 平均：O(n log n)
- 最坏：O(n²)（数组已序或逆序，每次划分仅减少一个元素）
- 空间复杂度：
- 最好/平均：O(log n)（递归栈深度为 log n）
- 最坏：O(n)（递归栈深度为 n）
5. 归并排序（Merge Sort）
- 时间复杂度：
- 最好/平均/最坏：O(n log n)（分治策略，每一层合并需 O(n)，共 log n 层）
- 空间复杂度：O(n)（合并时需额外数组存储临时结果）
6. 堆排序（Heap Sort）
- 时间复杂度：
- 最好/平均/最坏：O(n log n)（建堆 O(n)，每次调整堆 O(log n)，共 n 次）
- 空间复杂度：O(1)（原地排序，利用原数组构建堆）
7. 计数排序（Counting Sort）
- 时间复杂度：
- 最好/平均/最坏：O(n + k)（k 为数值范围，遍历数组 O(n) + 统计范围 O(k)）
- 空间复杂度：O(n + k)（需统计数组和输出数组）
8. 基数排序（Radix Sort）
- 时间复杂度：
- 最好/平均/最坏：O(d(n + k))（d 为最大数的位数，k 为基数，如十进制 k=10）
- 空间复杂度：O(n + k)（需临时数组存储每一位排序结果）
9. 桶排序（Bucket Sort）
- 时间复杂度：
- 最好：O(n + k)（数据均匀分布，桶内用线性排序）
- 平均：O(n + k)
- 最坏：O(n²)（所有数据集中在一个桶，退化为桶内排序复杂度）
- 空间复杂度：O(n + k)（需存储桶和临时数组）
复杂度对比表
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | \(\color{blue}{O(n)}\) | \(\color{green}{O(n^2)}\) | \(\color{green}{O(n^2)}\) | O(1) | 稳定 |
| 插入排序 | \(\color{blue}{O(n)}\) | \(\color{green}{O(n^2)}\) | \(\color{green}{O(n^2)}\) | O(1) | 稳定 |
| 选择排序 | \(\color{green}{O(n^2)}\) | \(\color{green}{O(n^2)}\) | \(\color{green}{O(n^2)}\) | O(1) | \(\color{red}{不稳定}\) |
| 快速排序 | \(\color{red}{O(n \log n)}\) | $\color{red}{O(n \log n)} $ | \(\color{green}{O(n^2)}\) | O(log n) | \(\color{red}{不稳定}\) |
| 归并排序 | \(\color{red}{O(n \log n)}\) | \(\color{red}{O(n \log n)}\) | \(\color{red}{O(n \log n)}\) | O(n) | 稳定 |
| 堆排序 | \(\color{red}{O(n \log n)}\) | \(\color{red}{O(n \log n)}\) | \(\color{red}{O(n \log n)}\) | O(1) | \(\color{red}{不稳定}\) |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | \(\color{green}{O(n^2)}\) | O(n + k) | 稳定 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 |
泡插选平方
泡茶选平方
快归堆 nlogn
快归队 nlogn
计桶n+k 基数d(n+k)
计桶n+k 基数再乘D
关键特性总结
- 稳定排序：冒泡、插入、归并、计数、基数、桶排序（桶内排序稳定时）。
- 原地排序：冒泡、选择、插入、快速、堆排序（空间复杂度 O(1) 或 O(log n)）。
- 线性时间排序：计数、基数、桶排序（需满足数值范围或分布条件）。