采用三数取中分区的快速排序无法正确排序，求问题排查

问题重现 #

以下是采用三数取中分区的快速排序代码，运行后输出数组未正确排序：

def medianof3(arr, low, high):
    center = (low + high) // 2
    if arr[low] < arr[center]:
        arr[low], arr[center] = arr[center], arr[low]

    if arr[low] < arr[high]:
        arr[low], arr[high] = arr[high], arr[low]

    if arr[center] < arr[high]:
        arr[center], arr[high] = arr[high], arr[center]

    arr[center], arr[high - 1] = arr[high - 1], arr[center]

    return arr[high - 1]


def partition(array, low, high):
    pivot = medianof3(array, low, high)
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i = i + 1
            (array[i], array[j]) = (array[j], array[i])

    (array[i + 1], array[high - 1]) = (array[high - 1], array[i + 1])
    return i + 1
 
def quickSort(array, low, high):
    if low < high:
        pi = partition(array, low, high)
        quickSort(array, low, pi - 1)
        quickSort(array, pi + 1, high)


data = [1, 7, 4, 1, 10, 9, -2]
print("未排序数组：")
print(data)
 
size = len(data)
quickSort(data, 0, size - 1)
 
print('升序排序后的数组：')
print(data)

错误输出：

未排序数组：
[1, 7, 4, 1, 10, 9, -2]
升序排序后的数组：
[1, 1, 7, 4, 9, 10, -2]

错误分析 #

1. 三数取中逻辑颠倒：原代码通过交换将较大元素前置，导致arr[low] >= arr[center] >= arr[high]，此时选取的基准虽为三个数的中位数，但arr[high]是三个数中的最小值，后续分区未处理该元素，导致它始终停留在末尾。
2. 分区循环范围错误：基准被放置在high-1位置后，原循环遍历low到high-1，既包含了本应小于等于基准的low位置元素，也包含了基准自身，可能引发无效交换；同时未利用三数取中后arr[high] >=基准的特性，导致该元素被遗漏。

修正后的代码 #

def medianof3(arr, low, high):
    center = (low + high) // 2
    # 调整三个位置元素为升序：arr[low] <= arr[center] <= arr[high]
    if arr[low] > arr[center]:
        arr[low], arr[center] = arr[center], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[center] > arr[high]:
        arr[center], arr[high] = arr[high], arr[center]
    # 将中位数（center位置）移到high-1，作为基准
    arr[center], arr[high-1] = arr[high-1], arr[center]
    return arr[high-1]


def partition(array, low, high):
    pivot = medianof3(array, low, high)
    # 左指针从low开始（因为arr[low] <= pivot）
    i = low
    # 右指针从high-2开始（因为arr[high-1]是基准，arr[high] >= pivot）
    j = high - 2

    while True:
        # 找到第一个大于pivot的元素
        while array[i] <= pivot:
            i += 1
        # 找到第一个小于pivot的元素
        while array[j] > pivot:
            j -= 1
        if i < j:
            array[i], array[j] = array[j], array[i]
        else:
            # 将基准放到正确位置
            array[i], array[high-1] = array[high-1], array[i]
            return i
 
def quickSort(array, low, high):
    # 当区间长度大于1时才排序，长度为1或0直接返回
    if high - low + 1 > 1:
        pi = partition(array, low, high)
        quickSort(array, low, pi - 1)
        quickSort(array, pi + 1, high)


data = [1, 7, 4, 1, 10, 9, -2]
print("未排序数组：")
print(data)
 
size = len(data)
quickSort(data, 0, size - 1)
 
print('升序排序后的数组：')
print(data)

正确输出：

未排序数组：
[1, 7, 4, 1, 10, 9, -2]
升序排序后的数组：
[-2, 1, 1, 4, 7, 9, 10]

修正说明 #

1. 修正三数取中逻辑：改为将三个位置的元素调整为升序，确保arr[low] <= pivot <= arr[high]，避免末尾出现未处理的小元素。
2. 优化分区逻辑：采用双向指针遍历，跳过已确定顺序的low和high位置元素，仅处理中间区间，提升效率同时避免遗漏元素。
3. 调整递归触发条件：仅当区间长度大于1时才递归，减少不必要的递归调用。

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