python - 尝试使用 python 实现快速排序，但它不起作用

Question

我正在尝试使用 python 实现快速排序算法我认为我已经完成了正确的步骤但是我的代码似乎有问题，每次我运行代码它都不起作用请你能帮我找到问题吗用我的代码。

def quicksort(alist,first,last):
    if first < last:
        split = partition(alist,first,last)

        quicksort(alist,first,split-1)
        quicksort(alist,split+1,last)



def partition(arr,first,last):

    pivot_val = arr[first]
    rightmark = first +1
    leftmark = last

    done = False

    while not done:

        while leftmark <= rightmark and arr[leftmark] <= pivot_val:
            leftmark +=1
        while arr[rightmark] >= pivot_val and rightmark >= leftmark:
            rightmark -=1

        if rightmark < leftmark:
            done = True
        else:
            tmp = arr[leftmark]
            arr[leftmark] = arr[rightmark]
            arr[rightmark] = tmp


    tmp = arr[rightmark]
    arr[rightmark] = arr[first]
    arr[first] = tmp

    return rightmark


lst = [22,54,33,11,87,76,1,3]

quicksort(lst,0,len(lst)-1)

print(lst)

输出看起来像这样:

[54, 22, 11, 33, 76, 87, 1, 3]

Answer 1

是的，通常的实现将枢轴作为最后一个值而不是第一个值，但这是无关紧要的。然而，错误是 rightmark 和 leftmark 的初始化。假设 leftmark 在“左”即小于，rightmark 大于，则 leftmark 应初始化为 first+1，rightmark 应初始化为 last。

这不是快速排序的正常实现，其分区函数简单地线性循环遍历数组(主元除外)。这个巧妙地将 leftmark 向右移动，直到第一个条目大于 pivot，然后将 rightmark 向左移动，直到它的第一个条目小于 pivot。然后它交换这两个值直到它们交叉。这就是结束条件。