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

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. 排序算法对比

排序算法	时间复杂度（最优）	时间复杂度（平均）	时间复杂度（最差）	空间复杂度	是否稳定	适用场景
快速排序	O(n log n)	O(n log n)	O(n²)（退化）	O(log n)	❌ 不稳定	适用于大规模数据，且数据较随机时性能较优
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ 稳定	适用于数据量较大且需要稳定性的情况，如链表排序、外部排序
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	❌ 不稳定	适用于 原地排序 且对 最坏情况 有较好保证的场景

---

5. 选择哪种排序？

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

推荐：

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

---

总结：

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