快速排序返回错误的顺序

Question

我正在使用 Python 递归实现快速排序，而无需创建新变量来保存分区数组的左右部分。

运行递归步骤时我得到了错误的值。这是我到目前为止所做的：

def swap(a,i,j):

    tmp = a[i]

    a[i] = a[j]

    a[j] = tmp

    

def pivot(a, lo, hi):

    mid = (lo + hi) // 2

    # sort lo, mid, hi:

    if a[mid] < a[lo]:

        swap(a, lo, mid)

    if a[hi] < a[lo]:

        swap(a, lo, hi)

    if a[hi] < a[mid]:

        swap(a, mid, hi)

def partition(a, lo, hi):

    # place the pivot out of the way, in position hi -1 

    mid = (lo + hi)//2

    swap(a, mid, hi - 1)

    

    i = lo

    j = hi - 1

    pivot = a[j]

    

    while True:

        while True:

            i += 1

            if a[i] >= pivot: break

           

        while True:

            j -= 1

            if a[j] <= pivot: break

            

            

        if i >= j: break

        swap(a, i, j)

    swap(a, i, hi - 1)

    return i

假设上面的模板代码是“正确的”。我必须使用上述枢轴和分区的实现来实现快速排序。这就是我所做的：

def quicksort(a):

    _sort(a, 0, len(a)-1)

    

def _sort(a, left, right):

    if(left <  right):

        pivot(a, left, right)

        piv = partition(a, left, right)

        _sort(a, left, piv-1)

        _sort(a, piv+1, right)

当我用列表调用快速排序时：

x = [98, 33, 11, 5, 1, 10, 11, 12, 14, 33, 55, 66, 556, 88]

quicksort(x)

print(x)

>>> [1, 5, 10, 11, 11, 12, 14, 33, 33, 55, 66, 88, 556, 98]

您可以看到 98 放错了位置。如果我这样跑：

x = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6, 55, 66, 888, 33, 556, 10]

quicksort(x)

print(x)

>>> [2, 3, 5, 6, 7, 9, 10, 10, 11, 12, 14, 33, 55, 66, 556, 888]

所以，对于上述情况来说，它是正确的。但在其他较小的情况下它会失败：

x = [98, 33, 11, 556, 88]

quicksort(x)

print(x)

>>> [33, 11, 88, 556, 98]

谁能帮我找到错误吗？谢谢 ：-）

Answer 1

我看到两个错误，第一个错误在您的partition()函数中。尝试替换swap(a, i, hi - 1)为swap(a, i, hi)第二个是在_sort(). 最后一次通话应该是_sort(a, piv, right)正确的代码是：def partition(a, lo, hi):&nbsp; &nbsp; # place the pivot out of the way, in position hi -1&nbsp;&nbsp; &nbsp; mid = (lo + hi)//2&nbsp; &nbsp; swap(a, mid, hi - 1)&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; i = lo&nbsp; &nbsp; j = hi - 1&nbsp; &nbsp; pivot = a[j]&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if a[i] >= pivot: break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j -= 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if a[j] <= pivot: break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if i >= j: break&nbsp; &nbsp; &nbsp; &nbsp; swap(a, i, j)&nbsp; &nbsp; swap(a, i, hi)&nbsp; &nbsp; return i和def _sort(a, left, right):&nbsp; &nbsp; if(left <&nbsp; right):&nbsp; &nbsp; &nbsp; &nbsp; pivot(a, left, right)&nbsp; &nbsp; &nbsp; &nbsp; piv = partition(a, left, right)&nbsp; &nbsp; &nbsp; &nbsp; _sort(a, left, piv-1)&nbsp; &nbsp; &nbsp; &nbsp; _sort(a, piv, right)测试：x = [98, 33, 11, 556, 88]quicksort(x)print(x)[11, 33, 88, 98, 556]更多测试：import randomfor n in range(10):&nbsp; &nbsp; x = [random.randint(1,999) for i in range(random.randint(4,10))]&nbsp; &nbsp; quicksort(x)&nbsp; &nbsp; print(x)[104, 226, 721, 769][131, 453, 590, 730, 752, 834][132, 156, 191, 277, 541, 599, 666, 909, 919][114, 210, 280, 919, 968, 978][127, 212, 381, 458, 585, 594, 685, 809, 935][73, 90, 189, 591, 599, 686, 806, 829, 831, 906][89, 115, 208, 601, 774, 813, 842, 981][159, 177, 203, 231, 621, 759, 950][347, 348, 417, 476, 850, 902][8, 50, 51, 483, 499, 696, 842]