尝试使用三中位数实现快速排序，但我不确定哪里出错了？

Question

尝试使用三中位数作为复习来实现快速排序，我使用以下算法：

唯一的区别是我尝试使用三个值（低、中值和高）的中间值而不是最左边的值作为基准 - 根据我的理解，这应该只改变几行代码，但出于某种原因，我的算法似乎没有正确排序，我不完全确定为什么？我试过按照它进行操作，但没有用——但我不太清楚哪里错了，为什么错了。我注意到我的第一个问题是不知何故，我的数组中的“0”在第一次分区传递时最终出现在完全错误的位置，我不知道为什么 - 不确定这是否会帮助任何人查明问题，但我我已经无计可施了，整天盯着这个看，一无所获。

def quicksort(arr, low, hi):
    def middle_of_three(arr, low, hi):
        mid = (low + hi) // 2
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        if arr[mid] > arr[hi]:
            arr[mid], arr[hi] = arr[hi], arr[mid]
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        return mid

    def partition(arr, low, hi):
        pivot = middle_of_three(arr, low, hi)  # get pivot index w/ median of three method
        left_wall = low
        for i in range(low + 1, hi):
            if arr[i] < arr[pivot]:
                arr[i], arr[left_wall] = arr[left_wall], arr[i]
                left_wall += 1
        arr[pivot], arr[left_wall] = arr[left_wall], arr[pivot]  # once you get to the end, swap pivot

        return left_wall

    if low < hi:
        pivot_loc = partition(arr, low, hi)
        quicksort(arr, low, pivot_loc)
        quicksort(arr, pivot_loc + 1, hi)
    print(sequence)


sequence = [2, 6, 5, 3, 8, 7, 1, 0]
size = len(sequence) - 1
quicksort(sequence, 0, size)

Answer 1

将middle_of_three改为return枢轴值而不是枢轴索引，并对其余代码进行类似的更改。 pivot 元素通常会在分区过程中移动，因此使用 pivot 值可以使代码更简单。

我不熟悉所使用的分区算法。通常分区扫描一对元素，其中 element > pivot 出现在 element < pivot 之前，并交换它们，重复该过程直到达到某个扫描限制。如果使用中间元素值作为主元值，通常会使用 Hoare 类型分区方案的变体。霍尔方案从左侧扫描元素 > 枢轴和从右侧扫描元素 < 枢轴，并在左右扫描的索引在数组中间某处相遇时停止。枢轴索引将基于索引相交的位置。

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

如果你仍然卡住了，我可以稍后在我的回答中添加一个 C/C++ 示例。

尝试使用三中位数实现快速排序，但我不确定哪里出错了？

Attempting to implement quicksort using median-of-three and I'm not sure where I'm going wrong?

python

quicksort