Python 中的快速排序实现 [特定输入崩溃]

Question

我正在写一个quick_sort算法代码。据我所知，这是应该工作的代码，它适用于大多数数组，但它不适用于 [5, 3, 9, 8, 6] 并吐出 IndexError: list index out of range

def quick_sort_array(A):
    return quick_sort(A, 0, len(A)-1)

def quick_sort(A, l, r):
    if l < r:
        pivot = A[l]
        left = l + 1
        right = r
        while left <= right:
            while A[left] <= pivot:
                left += 1
            while A[right] >= pivot and left <= right:
                right -= 1
            if left <= right:
                tmp = A[left]
                A[left] = A[right]
                A[right] = tmp
        A[l] = A[right]
        A[right] = pivot

        quick_sort(A, l, right-1)
        quick_sort(A, right+1, r)

你能帮我理解一下吗？谢谢

错误信息：

Answer 1

当主元是您正在分区的列表的开头部分和列表结尾之间的最大元素时，您的快速排序分区步骤的实现失败。增加 left 的 while 循环可以继续进行，直到它用完列表的末尾。

要解决此问题，您需要停止第一个内循环从运行过去 right，就像您已经阻止 right 从运行过去太远一样left。我还没有确切地验证你想要什么边界条件，但是从第二个内部循环复制一个可能会起作用：

        while A[left] <= pivot and left <= right:
            left += 1
        while A[right] >= pivot and left <= right:
            right -= 1

Python 中的快速排序实现 [特定输入崩溃]

Quick Sort Implementation in Python [particular input crashes]

python

sorting

algorithm