【排序算法对比】快速排序、归并排序、堆排序

排序算法对比：快速排序、归并排序、堆排序

1. 快速排序（Quick Sort）

原理

快速排序采用 分治法 （Divide and Conquer），通过选取基准值（pivot），将数组划分为 小于基准值 和 大于基准值 的两个部分，并递归排序。

特点

• 时间复杂度 ：
  • 最优： O(n log n)
  • 平均： O(n log n)
  • 最差： O(n²) （当选取的 pivot 总是最小或最大值时，会退化成冒泡排序）
• 空间复杂度 ： O(log n) （递归调用栈）
• 是否稳定 ：❌ 不稳定 （交换过程中可能改变相同元素的相对位置）
• 适用场景 ：
  • 适用于大规模数据排序
  • 数据较随机时性能较优
  • 不适用于数据接近有序 或 需要稳定性的场景

2. 归并排序（Merge Sort）

原理

归并排序同样采用 分治法 ，将数组拆分成 左右两部分 ，分别排序后再 合并（merge） ，确保整体有序。

特点

• 时间复杂度 ：
  • 最佳、最差、平均 ： O(n log n) （即使是最坏情况下也能保持 O(n log n) ）
• 空间复杂度 ： O(n) （额外存储归并时的数组）
• 是否稳定 ：✅ 稳定 （归并过程不会打乱相同元素的相对顺序）
• 适用场景 ：
  • 适用于 数据量大且需要稳定性 的情况
  • 适用于 链表排序
  • 适用于 外部排序（大数据排序） ，因其可并行处理数据

3. 堆排序（Heap Sort）

原理

堆排序基于 二叉堆（Binary Heap） 数据结构，先将数组构造成 最大堆（Max Heap） ，然后依次取出堆顶元素（最大值），调整堆结构，最终得到一个有序数组。

特点

• 时间复杂度 ：
  • 最优、平均、最差： O(n log n)
• 空间复杂度 ： O(1) （原地排序，不需要额外空间）
• 是否稳定 ：❌ 不稳定 （堆调整过程中可能改变相同元素的相对位置）
• 适用场景 ：
  • 适用于 大规模数据排序
  • 适用于 对最坏情况有较好保证 的场景
  • 适用于 优先队列的实现

4. 排序算法对比

5. 选择哪种排序？

• 快速排序 ：一般情况下最快，适用于数据规模大、数据随机分布的情况。
• 归并排序 ：适用于数据量大、 稳定性要求高 的情况，如数据库排序。
• 堆排序 ：适用于 大规模数据排序 ，适用于 时间复杂度需要稳定的情况 。

推荐：

• 如果 数据量大 ，推荐 快速排序 （但注意避免最坏情况）。
• 如果 要求稳定排序 ，推荐 归并排序 。
• 如果 空间受限 ，推荐 堆排序 （因为它是 O(1) 空间复杂度的 O(n log n) 排序算法）。

总结：

1. 快速排序 是平均情况下最快的 O(n log n) 排序，但最坏情况下退化为 O(n²) 。
2. 归并排序 始终 是 O(n log n) ，但需要额外 O(n) 空间，是稳定排序。
3. 堆排序 适用于 大数据且需要 O(1) 额外空间 ，但不稳定。