python - 以中间元素为轴心进行快速排序

Question

我有这个代码，但雇主要求我在中间调整如果有人可以提供帮助，请编辑此代码

def quicksort(sequence, low, high):
    if low < high:
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

Answer 1

patel 的回答从问题的 Lomuto 方案切换到 Hoare 方案。问题代码的最简单修复方法是将中间元素与低元素交换为分区中的第一行

def partition(sequence, low, high):
    sequence[low],sequence[(low+high)//2] = sequence[(low+high)//2],sequence[low] #change
    pivot = sequence[low]
      ...