实现按数组元素数量选择枢轴策略的快速排序优化

针对需求，我们对快速排序的枢轴选择逻辑进行了优化：

• 当子数组元素数量小于1000时，继续使用三数取中策略
• 当子数组元素数量≥1000时，选取21个等间距采样元素的中位数作为枢轴，以此降低极端数据分布下的排序复杂度

以下是完整的实现代码：

def quickSort(ele, ascending=True):
    quicksorthelp(ele, 0, len(ele), ascending)

def mediana(ele, primeiro, ultimo):
    mid = (primeiro + ultimo - 1) // 2
    a = ele[primeiro]
    b = ele[mid]
    c = ele[ultimo - 1]
    if a <= b <= c:
        return b, mid
    if c <= b <= a:
        return b, mid
    if a <= c <= b:
        return c, ultimo - 1
    if b <= c <= a:
        return c, ultimo - 1
    return a, primeiro

def median_of_21(ele, primeiro, ultimo):
    # 生成21个等间距的采样索引
    step = (ultimo - primeiro - 1) // 20
    samples = []
    for i in range(21):
        idx = primeiro + i * step
        samples.append((ele[idx], idx))
    # 对采样元素排序，取中位数（第10个元素，索引从0开始）
    samples.sort()
    return samples[10][0], samples[10][1]

def select_pivot(ele, primeiro, ultimo):
    length = ultimo - primeiro
    if length < 1000:
        return mediana(ele, primeiro, ultimo)
    else:
        return median_of_21(ele, primeiro, ultimo)

def quicksorthelp(ele, primeiro, ultimo, ascending=True):
    result = 0
    if primeiro < ultimo:
        pivot_location, result = Partition(ele, primeiro, ultimo, ascending)
        result += quicksorthelp(ele, primeiro, pivot_location, ascending)
        result += quicksorthelp(ele, pivot_location + 1, ultimo, ascending)
    return result

def Partition(ele, primeiro, ultimo, ascending=True):
    result = 0
    # 替换为新的枢轴选择函数
    pivot, pidx = select_pivot(ele, primeiro, ultimo)
    ele[primeiro], ele[pidx] = ele[pidx], ele[primeiro]
    i = primeiro + 1
    for j in range(primeiro + 1, ultimo, 1):
        result += 1
        if (ascending and ele[j] < pivot) or (not ascending and ele[j] > pivot):
            ele[i], ele[j] = ele[j], ele[i]
            i += 1
    ele[primeiro], ele[i - 1] = ele[i - 1], ele[primeiro]
    return i - 1, result

# 输入与输出逻辑
arr = []
tam = int(input(""))

for i in range(tam):
    ele = int(input(""))
    arr.append(ele)

quickSort(arr, True)
for num in arr:
    print(num)

关键修改说明 #

1. 新增select_pivot函数：作为枢轴选择的统一入口，根据当前子数组长度动态切换策略
2. 新增median_of_21函数：
   • 计算21个等间距采样点的索引，确保覆盖整个子数组范围
   • 对采样的(元素值, 索引)元组排序，取中间位置的元素作为枢轴
3. 修改Partition函数：将原有的mediana调用替换为select_pivot，实现策略的无缝切换

内容的提问来源于stack exchange，提问作者André Cunha