以下是常见排序算法的性能对比及选择依据总结：
| 排序方法 | 时间复杂度 | 辅助空间 | 稳定性 |
|---|---|---|---|
| 直接插入 | O(n²) | O(1) | 稳定 |
| 简单选择 | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(1) | 不稳定 |
| 快速排序 | O(n log n) 平均 | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n) | 稳定 |
| 基数排序 | O(d(n + rd)) | O(rd) | 稳定 |
排序算法选择依据
当 n 较小时（如 n < 50）：
- 推荐使用直接插入排序或简单选择排序。
- 若记录信息量较大（移动代价高），优先选简单选择排序（减少交换次数）。
当关键字基本有序时：
- 直接插入排序和冒泡排序表现优异，尤其是直接插入在接近有序时接近 O(n)。
当 n 大且关键字位数少（如整数、字符串等可分解位）：
- 可考虑链式基数排序，尤其适用于固定长度的关键字（如电话号码、学号）。
当 n 较大时：
- 优先选择时间复杂度为O(n log n)的算法：
- 快速排序：平均性能最优，但最坏情况退化为 O(n²)，不稳定。
- 堆排序：时间稳定 O(n log n)，空间仅 O(1)，适合内存受限场景，但不稳定。
- 归并排序：唯一稳定的 O(n log n) 算法，适合要求稳定性的外部排序或链表排序，但需 O(n) 额外空间。
- 优先选择时间复杂度为O(n log n)的算法：
总结建议
- 追求速度且无稳定性要求→ 快速排序（注意优化基准选择）
- 需要稳定性且允许额外空间→ 归并排序
- 内存紧张但需高效→ 堆排序
- 数据规模小或近似有序→ 直接插入 / 冒泡
- 特定数据结构（如链表）或关键字可分位→ 基数排序
快速排序的平均时间复杂度为O(n log n)，而最坏情况下退化为O(n²)，其根本原因在于基准元素（pivot）的选择以及由此导致的划分不平衡程度。
1. 基本思想回顾
快速排序采用分治法：
- 选取一个基准（pivot），将数组划分为两部分：小于 pivot 的放在左边，大于的放在右边。
- 递归地对左右子数组进行快排。
设每次划分耗时 O(n)，若能均匀分割，则递归深度为 O(log n)，总时间复杂度为：
T(n) = 2T(n/2) + O(n) → O(n log n)这就是平均情况的时间复杂度。
2. 平均情况：O(n log n)
在随机数据中，假设我们随机选择 pivot或使用“三数取中”等策略，则每次划分大概率接近均分。数学期望下，每层平均处理所有元素一次，递归树深度约为 log n 层。
因此，平均时间复杂度为 O(n log n)。
3. 最坏情况：O(n²)
当每次选择的 pivot 是当前数组中的最大值或最小值时，会导致极端不均衡的划分：
- 一边有 n−1 个元素，另一边为空。
- 每次只能排除一个元素，递归深度达到 n 层。
- 总体时间变为：
T(n) = T(n−1) + O(n) → O(n²)典型场景包括：
- 数组已经有序（升序或降序）
- 每次选第一个或最后一个元素作 pivot
- 所有元素相等（未优化重复键）
例如：对[1,2,3,4,5]使用首元素为 pivot，每次划分都极不平衡。
4. 如何避免最坏情况？
| 方法 | 效果 |
|---|---|
| 随机化 pivot | 使最坏情况具有偶然性，期望性能稳定 |
| 三数取中法（mid of three） | 减少在有序数据上选到极值的概率 |
| 双轴快排（如 Java 中的 Dual-Pivot Quicksort） | 提高分区效率，尤其对重复元素多的数据 |
✅总结：
快速排序平均性能优秀是因为划分较均衡，递归深度小；而最坏情况发生在每次划分极度不平衡时（如已排序数据），导致递归深度达 n，从而使总时间退化为 O(n²)。
