以下是对常见排序算法的特点及时间/空间复杂度对比表格，结合了不同应用场景和算法特性，便于记忆和理解：
排序算法对比表（按时间复杂度升序排列）
| 排序算法 | 类别 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | 比较类 | O(n²) | O(n) 3 | O(n²) | O(1) | 稳定 | 小数据量或近乎有序数据 3 |
| 插入排序 | 比较类 | O(n²) | O(n) 3 | O(n²) | O(1) | 稳定 | 小数据量、近乎有序数据 3 |
| 选择排序 | 比较类 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 简单实现，内存受限场景 1 |
| 快速排序 | 比较类 | O(n log n) | O(n log n) | O(n²) 3 | O(log n) | 不稳定 | 大数据量、随机分布数据 3 |
| 归并排序 | 比较类 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 大数据量、稳定性要求高 1 |
| 堆排序 | 比较类 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存受限的大数据场景 3 |
| 希尔排序 | 比较类（改进插入） | O(n log n)~O(n²) | O(n log n) | O(n²) | O(1) | 不稳定 | 中等数据量，非稳定性需求 4 |
| 计数排序 | 非比较类 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 | 整数数据且范围较小 1 |
| 桶排序 | 非比较类 | O(n + k) | O(n + k) | O(n²) | O(n + k) | 稳定 | 均匀分布的数据 1 |
| 基数排序 | 非比较类 | O(n × k) | O(n × k) | O(n × k) | O(n + k) | 稳定 | 多关键字排序（如字符串） 1 |
关键特性说明
-
稳定性
-
时间复杂度
-
空间复杂度
-
非比较类排序
- 通过数值特性（如计数、桶划分）突破O(n log n)下限，但仅适用于特定数据范围1。
记忆技巧
- O(n²)算法：冒泡、插入、选择（适合小数据量）。
- O(n log n)算法：快速、归并、堆排序（适合大数据量）。
- 线性时间算法：计数、桶、基数排序（需数据满足特定条件）。
- 稳定性口诀：“插归冒基计桶”（插入、归并、冒泡、基数、计数、桶排序）是稳定的1。
网友评论