改进快速排序处理大量重复元素的随机交换法为何未被广泛采用？

当数组全为重复元素时，传统快速排序无论选择何种枢轴，都会产生大小为1和n-1的极端不平衡分区，导致时间复杂度退化为O(n²)。你提出的改进方案是在分区过程中，遇到与枢轴相等的元素时，以50%的概率将其视为“小于”或“大于”枢轴，以此让重复元素均匀分布在枢轴两侧，对应的分区代码如下：

def partition(arr: list[int]):
  pivot = arr[-1]
  current_index = 0
  for i in range(len(arr) - 1):
    if arr[i] < pivot or (arr[i] == pivot and random.random() < 0.5):
      arr[i], arr[current_index] = arr[current_index], arr[i]
      current_index += 1
  # 将枢轴放到正确位置
  arr[-1], arr[current_index] = arr[current_index], arr[-1]
  # 返回分区索引
  return current_index

（核心逻辑是arr[i] == pivot and random.random() < 0.5的随机判断）

但这个方案并未被广泛采用，主要有以下几个原因：

• 随机数生成的额外开销：每次遇到与枢轴相等的元素都要调用随机数生成器，这个操作的开销远大于普通的比较、交换操作。当数组中重复元素占比很高时，大量的随机调用会显著拖慢排序的实际运行速度，理论复杂度的优化抵不过实际性能的下降。

• 分区稳定性不足：虽然从概率期望上看重复元素会均匀分布，但实际运行中仍存在极端情况（比如连续多次随机结果偏向同一侧），导致分区依然不平衡，最坏时间复杂度仍有概率落到O(n²)，不如确定性的改进方案可靠。

• 已有更优的成熟替代方案：目前工业界和算法实践中，针对重复元素问题普遍使用三路快速排序——直接将数组划分为「小于枢轴」「等于枢轴」「大于枢轴」三个部分，所有等于枢轴的元素直接归位，不需要任何随机操作，分区绝对稳定，在重复元素多的场景下时间复杂度稳定为O(nlogn)，实现成本也不高，完全覆盖了你这个方案的需求，且性能更优。

本质上你的方案是用随机化来模拟三路分区的效果，但付出了额外的随机开销，还不如直接采用三路分区来得高效直接。

内容的提问来源于stack exchange，提问作者distributer