排序算法核心总结
2025-08-24 14:13:40
发布于:上海
一、核心分类标准
-
比较排序
▸ 必须通过元素两两比较
▸ 理论下限:O(n log n)
▸ 典型算法:快速排序、归并排序 -
非比较排序
▸ 利用数据特殊属性(如数值范围)
▸ 可突破O(n log n)限制
▸ 典型算法:计数排序、基数排序
空间复杂度
-
原地排序
- 空间复杂度≤O(1)
- 示例:冒泡排序、插入排序
-
非原地排序
- 需要额外存储空间
- 示例:归并排序(O(n))、基数排序(O(n+k))
二、排序算法性能对比表
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✔ | 教学演示/小规模数据 |
| 插入排序 | O(n²) | O(n²) | O(1) | ✔ | 近乎有序数据/小规模 |
| 选择排序 | O(n²) | O(n²) | O(1) | ✖ | 交换成本高的场景 |
| 希尔排序 | O(n^(6/5)) | O(n²) | O(1) | ✖ | 中等规模数据 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ✖ | 通用大规模数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✔ | 稳定排序/外部排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ✖ | 内存受限场景 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | ✔ | 整数且范围较小 |
| 基数排序 | O(dn) | O(dn) | O(n + k) | ✔ | 多关键字排序 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | ✔ | 均匀分布数据 |
三、选择建议
- 小数据:优先选择插入排序
- 大数据量:快速排序(需优化基准选择)或归并排序
- 稳定性要求:归并排序或计数排序
这里空空如也













有帮助,赞一个