快速排序与归并排序的比较

题目描述
快速排序和归并排序都是基于分治思想的高效排序算法，平均时间复杂度均为 \(O(n \log n)\)。但在实际应用中，两者的性能表现、稳定性和适用场景有显著差异。面试中常要求对比两者的核心思想、时间复杂度、空间复杂度、稳定性及优化策略。

解题过程

1. 核心思想对比

• 快速排序：
  • 分治策略：选择一个基准值（pivot），将数组划分为左右两部分，左边均小于等于基准，右边均大于等于基准，递归处理左右子数组。
  • 关键操作：划分（Partition），需保证基准值的位置最终确定。
• 归并排序：
  • 分治策略：将数组平分为两部分，分别递归排序，再将两个有序数组合并为一个有序数组。
  • 关键操作：合并（Merge），需额外空间存储合并结果。

2. 时间复杂度分析

• 平均情况：两者均为 \(O(n \log n)\)。
• 最坏情况：
  • 快排：当数组已有序或逆序，且基准选择不当时（如总选第一个元素），退化为 \(O(n^2)\)。
  • 归并：始终严格平分数组，最坏仍为 \(O(n \log n)\)。
• 优化策略：
  • 快排通过随机选择基准或三数取中法避免最坏情况。
  • 归并无需特别优化，但递归深度固定为 \(\log n\)。

3. 空间复杂度分析

• 快排：
  • 递归栈深度平均为 \(O(\log n)\)，最坏 \(O(n)\)。
  • 原地排序，无需额外存储数据，但递归调用占用栈空间。
• 归并：
  • 需额外 \(O(n)\) 空间存储合并后的数组（递归实现）。
  • 若采用非递归迭代实现，可减少栈空间，但仍需 \(O(n)\) 辅助数组。

4. 稳定性对比

• 快排：不稳定。划分过程中可能改变相等元素的相对顺序（如交换操作跨越相等元素）。
• 归并：稳定。合并时若遇到相等元素，优先保留左半部分元素顺序。

5. 适用场景

• 快排：
  • 一般情况下的首选，缓存友好（局部性原理），常数因子较小。
  • 对内存敏感的场景（如嵌入式系统），因原地排序特性。
• 归并：
  • 需稳定排序时（如数据库排序）。
  • 链表排序更高效（无需随机访问，合并操作天然适合链表）。
  • 外部排序（数据量太大无法全部加载到内存）。

6. 代码实现特点

• 快排：
  • 分区函数需高效实现（如 Lomuto 或 Hoare 划分）。
  • 递归终止条件为子数组长度 ≤ 1。
• 归并：
  • 合并函数需遍历两个子数组，比较后填入辅助数组。
  • 递归终止条件为数组长度 ≤ 1。

总结

• 快排的平均性能更优，但需注意最坏情况；归并排序稳定且时间复杂度稳定，但空间开销较大。
• 选择依据：数据特征（是否接近有序）、稳定性要求、内存限制、数据结构（数组 vs 链表）。