排序算法进阶总结 | 技巧归纳与实战应用
排序算法进阶总结 | 技巧归纳与实战应用
引言
排序是计算机科学中最基础的问题之一，也是面试中的高频考点。本文将对排序算法进行进阶总结，包括各种排序算法的特点、应用场景和优化技巧。
排序算法分类
基于比较的排序
基于比较的排序通过比较元素之间的大小关系来确定顺序，时间复杂度下界是 O(n log n)。
经典算法：
- O(n²)：冒泡排序、选择排序、插入排序
- O(n log n)：归并排序、快速排序、堆排序
非比较排序
非比较排序不通过比较来确定顺序，适用于特定类型的数据。
经典算法：
- O(n + k)：计数排序（k 是数据范围）
- O(n)：基数排序、桶排序
排序算法高级技巧
自定义排序
自定义排序是解决特殊问题的关键，如 LeetCode 179（最大数）使用自定义比较函数来确定数字的排列顺序。
三路分区
三路分区是快速排序的变种，将数组分为小于 pivot、等于 pivot 和大于 pivot 三部分。适用于存在大量重复元素的情况。
原地排序
原地排序只使用 O(1) 的额外空间。堆排序是原地排序，但快速排序需要 O(log n) 的递归栈空间。
排序与其他算法的结合
归并排序与其他问题
归并排序可以用于解决逆序对、翻转对等问题。在归并过程中，可以统计满足特定条件的元素对。
桶排序与区间问题
桶排序适用于数据分布均匀的情况，可以用于解决最大间距等问题。
堆排序与 Top K 问题
堆排序适用于需要频繁获取最大或最小元素的问题。可以在 O(n log k) 时间内解决 Top K 问题。
常见面试题类型
排序后处理
先排序再处理是常见模式，如求最大数、第 K 大元素等。
原地修改
使用特定排序方法在原地修改数组，如颜色分类、摆动排序。
统计问题
在排序过程中统计信息，如逆序对计数。
时间复杂度对比
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
空间复杂度对比
| 算法 | 空间复杂度 |
|---|---|
| 冒泡排序 | O(1) |
| 选择排序 | O(1) |
| 插入排序 | O(1) |
| 归并排序 | O(n) |
| 快速排序 | O(log n) |
| 堆排序 | O(1) |
稳定性分析
稳定排序：冒泡排序、插入排序、归并排序
不稳定排序：选择排序、快速排序、堆排序
实际应用场景
需要稳定排序
当排序后需要保持相等元素的相对顺序时，使用稳定排序算法。
内存受限
当内存受限且需要排序时，使用堆排序等原地排序算法。
时间要求严格
当时间要求严格且数据分布均匀时，使用桶排序等线性时间排序。
面试中的常见问题
Q1: 快速排序最坏情况是什么？如何优化？
最坏情况发生在数组已经有序或完全逆序时。优化方法：
- 随机选择 pivot
- 三数取中法
- 当子数组大小较小时切换到插入排序
Q2: 归并排序和快速排序的区别？
归并排序稳定，快速排序不稳定。归并排序需要 O(n) 额外空间，快速排序只需要 O(log n)。快速排序的最坏情况是 O(n²)，但平均是 O(n log n)。
Q3: 什么情况下应该使用堆排序而不是快速排序？
当需要稳定性或内存受限时。堆排序是原地排序，空间复杂度 O(1)。
总结
排序算法是算法学习的基础。不同排序算法有各自的优缺点：
- 数据基本有序时，插入排序效率最高
- 需要稳定排序时，归并排序是首选
- 通用场景下，快速排序通常最优
- 数据范围已知且不大时，计数排序可达线性时间
掌握各种排序算法的原理、复杂度和适用场景，对于提升算法能力和应对面试都有重要意义。