以下是七种经典排序算法的时间复杂度和空间复杂度总结，结合各算法特性和搜索结果分析如下：
一、直接插入排序
- 时间复杂度
- 最好情况：O(n)（数组已有序，仅需比较n-1次）
- 平均/最坏情况：O(n²)（需要逐次后移元素）
- 空间复杂度：O(1)（仅需常数级辅助空间）
适用场景：小规模数据或基本有序的数组。
二、希尔排序
- 时间复杂度
- 平均情况：O(n log² n)（依赖增量序列，如Hibbard序列为O(n^(3/2))）
- 最坏情况：O(n²)（如使用较差增量序列）
- 空间复杂度：O(1)（原地排序）
特点：分组插入排序，通过缩小增量逐步优化局部有序性。
三、冒泡排序
- 时间复杂度
- 最好情况：O(n)（数组已有序，仅需1轮遍历）
- 平均/最坏情况：O(n²)（需n-1轮比较交换）
- 空间复杂度：O(1)（仅需交换辅助变量）
优化：可设置标志位提前终止，减少无效循环。
四、快速排序
- 时间复杂度
- 平均/最好情况：O(n log n)（基于分治思想，每次均匀划分）
- 最坏情况：O(n²)（如数组完全有序，基准选择不当）
- 空间复杂度：O(log n)（递归栈深度）
优化：三数取中法选择基准，避免最坏情况。
五、直接选择排序
- 时间复杂度
- 所有情况：O(n²)（需n(n-1)/2次比较）
- 空间复杂度：O(1)（原地交换）
缺点：不稳定，每次选择最小/最大值时可能破坏相等元素顺序。
六、堆排序
- 时间复杂度
- 所有情况：O(n log n)（建堆O(n)，每次调整堆O(log n)）
- 空间复杂度：O(1)（无需额外空间，原地构建堆）
核心操作：通过构建最大堆/最小堆实现排序，适合大规模数据。
七、基数排序
- 时间复杂度
- 所有情况：O(d(n + k))（d为最大位数，k为基数范围，如十进制k=10）
- 空间复杂度：O(n + k)（需k个桶存储中间结果）
适用场景：非负整数或定长字符串排序，如大数据量的多关键字排序。
综合对比
| 排序算法 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n log n) | O(n log² n) | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 直接选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 |
关键结论
- 时间效率：快速排序和堆排序在平均情况下表现最优（O(n log n)），但快速排序在最坏情况下需优化基准选择。
- 空间效率：直接插入、冒泡、选择排序和希尔排序适合内存受限场景（O(1)）。
- 稳定性：基数排序和直接插入排序适用于需保留原始顺序的场景。
根据数据特征和需求选择合适的算法，例如小数据用插入排序，大数据用快速排序或堆排序，多位数整数用基数排序。
评论区