快速排序的稳定性分析与优化

题目描述
快速排序是一种高效的排序算法，平均时间复杂度为O(n log n)，但传统实现是不稳定的。本题要求深入分析快速排序不稳定的原因，并探讨如何通过优化使其成为稳定排序，同时比较优化后的性能代价。

稳定性概念回顾
稳定性指相等元素在排序后相对顺序保持不变。例如，对(3, 2, 2')排序后若保持2在2'之前，则算法稳定。快速排序的经典实现中，划分时可能改变相等元素的原始顺序。

不稳定性原因分析

1. 划分操作中的交换：当选择基准pivot后，扫描过程中遇到与pivot相等的元素时，可能因交换操作改变顺序。
   • 示例：数组[3, 2, 2']，以第一个元素3为基准。左指针找到2，右指针找到2'，交换后变为[3, 2', 2]，相等元素2和2'顺序颠倒。
2. 基准选择位置：若基准是重复元素之一，划分时可能将其与其它相等元素交换。

优化实现稳定性的方法
方法一：三路划分（Three-Way Partitioning）

• 将数组划分为三部分：小于pivot、等于pivot、大于pivot。
• 步骤：
  1. 初始化指针lt、i、gt，使得[0, lt) < pivot，[lt, i) = pivot，[gt, n] > pivot。
  2. 遍历时若当前元素小于pivot，交换到lt区间；若大于pivot，交换到gt区间；若相等则直接移动i指针。
  3. 相等元素区间保持原顺序，因不参与交换。
• 代码框架：

  def stable_quicksort(arr, low, high):
      if low >= high:
          return
      lt, i, gt = low, low, high
      pivot = arr[low]  # 可选随机化基准
      while i <= gt:
          if arr[i] < pivot:
              arr[lt], arr[i] = arr[i], arr[lt]
              lt += 1
              i += 1
          elif arr[i] > pivot:
              arr[i], arr[gt] = arr[gt], arr[i]
              gt -= 1
          else:
              i += 1
      stable_quicksort(arr, low, lt - 1)
      stable_quicksort(arr, gt + 1, high)
  

• 稳定性保证：相等元素被保留在中间区间，相对顺序不变。

方法二：使用额外空间（非原地排序）

• 创建临时数组，划分时将小于、等于、大于pivot的元素分别存入三个列表，按顺序合并后递归处理。
• 优点：简单直观，严格稳定；缺点：空间复杂度O(n)。

性能代价分析

1. 三路划分优化：
   • 优点：对含重复元素的数组效率更高（复杂度接近O(n)）；保持稳定性。
   • 代价：代码稍复杂；常数因子可能略高于经典双路划分。
2. 额外空间方法：
   • 代价：空间开销大，违背快速排序的原地特性。

工程实践建议

• 若需稳定排序且允许额外空间，可考虑归并排序。
• 快速排序的稳定性优化适用于特定场景（如多键排序），但一般场景下更关注其平均性能。

总结
通过三路划分或非原地方法可实现稳定快速排序，但需权衡性能与空间。理解稳定性根源有助于在面试中展现对算法细节的深入掌握。