优化快速排序处理重复元素：分区策略对比分析

import random

def partition_with_randomized_duplicates(arr: list[int], low: int, high: int) -> int:
    """
    Lomuto-style partition with randomized handling of elements equal to the pivot.
    The pivot is chosen as the last element.
    """
    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_duplicates(arr: list[int], low: int, high: int):
    """
    Quick Sort implementation using the randomized duplicates partition scheme.
    """
    if low < high:
        # 获取分区点
        pi = partition_with_randomized_duplicates(arr, low, high)
        # 递归对左右两部分进行排序
        quick_sort_randomized_duplicates(arr, low, pi - 1)
        quick_sort_randomized_duplicates(arr, pi + 1, high)

# 示例用法：
# my_list = [3, 2, 3, 1, 3, 2, 3, 3]
# quick_sort_randomized_duplicates(my_list, 0, len(my_list) - 1)
# print(my_list) # 输出: [1, 2, 2, 3, 3, 3, 3, 3] (顺序可能因随机性略有不同)

def partition_hoare(arr: list[int], low: int, high: int) -> int:
    """
    Hoare partition scheme.
    The pivot is chosen as the first element.
    """
    pivot = arr[low] # 通常选择第一个元素作为基准
    i = low - 1
    j = high + 1

    while True:
        # 从左向右找到第一个大于或等于基准的元素
        i += 1
        while arr[i] < pivot:
            i += 1

        # 从右向左找到第一个小于或等于基准的元素
        j -= 1
        while arr[j] > pivot:
            j -= 1

        # 如果指针交叉，则分区完成
        if i >= j:
            return j # 返回分区点

        # 交换找到的元素
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_hoare(arr: list[int], low: int, high: int):
    """
    Quick Sort implementation using the Hoare partition scheme.
    """
    if low < high:
        # Hoare分区返回一个索引j，使得arr[low...j]和arr[j+1...high]是两个分区。
        # 基准元素本身可能不在j的位置，但j定义了分割点。
        pi = partition_hoare(arr, low, high)
        quick_sort_hoare(arr, low, pi) # 注意：pi包含在左子数组中
        quick_sort_hoare(arr, pi + 1, high)

# 示例用法：
# my_list = [3, 2, 3, 1, 3, 2, 3, 3]
# quick_sort_hoare(my_list, 0, len(my_list) - 1)
# print(my_list) # 输出: [1, 2, 2, 3, 3, 3, 3, 3]