三路划分快速排序实现问询：含大量重复元素场景优化

作为算法初学者，你选三路划分（3-way partition）来优化重复元素多的快排效率，这个思路特别到位！三路划分能把等于基准值的元素直接归位，避免对这部分元素重复递归，完美解决普通快排在重复元素密集场景下的性能问题。我帮你把未完成的partition3函数补全，再拆解下核心逻辑：

完整实现代码 #

import random

def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    # 随机选择基准元素，避免有序数组导致的最坏时间复杂度
    k = random.randint(l, r)
    a[l], a[k] = a[k], a[l]
    # 执行三路划分，得到等于基准值区域的左右边界
    m1, m2 = partition3(a, l, r)
    # 仅对小于基准和大于基准的区域递归排序
    randomized_quick_sort(a, l, m1 - 1)
    randomized_quick_sort(a, m2 + 1, r)

def partition3(a, l, r):
    x = a[l]  # 基准值（已通过随机交换放到左边界）
    j = l     # 小于基准值区域的右边界
    t = r     # 大于基准值区域的左边界
    i = l     # 当前遍历的指针

    while i <= t:
        if a[i] < x:
            # 当前元素小于基准，交换到小于区域的下一个位置
            a[i], a[j] = a[j], a[i]
            j += 1
            i += 1
        elif a[i] > x:
            # 当前元素大于基准，交换到大于区域的前一个位置
            a[i], a[t] = a[t], a[i]
            t -= 1
        else:
            # 当前元素等于基准，直接留在中间区域，指针右移
            i += 1
    # 返回等于基准值区域的左右边界
    return j, t

核心逻辑拆解 #

• 随机基准选择：通过random.randint(l, r)随机挑选元素和左边界交换，避免数组有序时快排时间复杂度退化为O(n²)，保证平均时间复杂度稳定在O(n log n)。
• 三路划分的区域维护：
  • [l, j-1]：存放小于基准值的元素
  • [j, t]：存放等于基准值的元素（这部分不需要再递归）
  • [t+1, r]：存放大于基准值的元素
• 遍历指针的处理逻辑：
  • 遇到小于基准的元素，交换到小于区域，同时扩张小于区域边界并移动遍历指针
  • 遇到大于基准的元素，交换到大于区域，仅收缩大于区域边界（因为交换过来的元素还未检查）
  • 遇到等于基准的元素，直接跳过，留在中间区域

测试示例 #

# 测试包含大量重复元素的数组
test_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 5, 5]
randomized_quick_sort(test_array, 0, len(test_array)-1)
print(test_array)
# 输出结果：[1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 5, 6, 9]

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