优化快速排序以应对大量重复数据：分区策略深度解析

import random

def partition_with_randomized_duplicates(arr: list[int], low: int, high: int) -> int:
  """
  使用随机化策略处理重复元素的分区函数（Lomuto风格）。
  与枢轴相等的元素，通过随机选择将其归入“小于”或“大于”分区。
  """
  pivot = arr[high]  # 选择最后一个元素作为枢轴
  current_index = low # current_index 追踪小于枢轴的元素的边界

  for i in range(low, high):
    # 如果当前元素小于枢轴，或者当前元素等于枢轴且随机选择将其视为“小于”
    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[high], arr[current_index] = arr[current_index], arr[high]
  return current_index

def quick_sort_randomized(arr: list[int], low: int, high: int):
  """
  基于随机化分区策略的快速排序实现。
  """
  if low < high:
    pi = partition_with_randomized_duplicates(arr, low, high)
    quick_sort_randomized(arr, low, pi - 1)
    quick_sort_randomized(arr, pi + 1, high)

# 示例用法
# my_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
# quick_sort_randomized(my_array, 0, len(my_array) - 1)
# print(my_array) # 输出: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

def three_way_partition(arr: list[int], low: int, high: int) -> tuple[int, int]:
    """
    三路分区函数，返回等于枢轴元素的范围 (lt, gt)。
    分区后，数组结构为：
    [low ... lt-1] < pivot
    [lt ... gt] == pivot
    [gt+1 ... high] > pivot
    """
    if high < low:
        return low, high

    pivot = arr[low] # 通常选择第一个元素作为枢轴
    lt = low         # 'less than' 区域的右边界
    gt = high        # 'greater than' 区域的左边界
    i = low + 1      # 当前正在检查的元素

    while i <= gt:
        if arr[i] < pivot:
            arr[i], arr[lt] = arr[lt], arr[i]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else: # arr[i] == pivot
            i += 1
    return lt, gt

def quick_sort_three_way(arr: list[int], low: int, high: int):
    """
    基于三路分区策略的快速排序实现。
    """
    if low < high:
        lt, gt = three_way_partition(arr, low, high)
        quick_sort_three_way(arr, low, lt - 1)
        quick_sort_three_way(arr, gt + 1, high)

# 示例用法
# my_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
# quick_sort_three_way(my_array, 0, len(my_array) - 1)
# print(my_array) # 输出: [1, 1, 2, 3, 3, 5, 5, 5, 6, 9, 4] (注意枢轴选择和实现细节可能影响最终顺序)