这个快速排序算法实现有什么问题？

Question

我正在尝试实现快速排序算法，选择最右边的元素作为枢轴，如Cormey等人所述，《算法导论》：

以下是我的Python实现：

def partition(A, p, r):
    pivot = A[r]
    i = p - 1
    for j in range(p, r-1):
        if A[j] < pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

然而，如果我这样测试它：

A = [2, 8, 7, 1, 3, 5, 6, 4]
quicksort(A, 0, len(A)-1)
print(A)

我得到了一个未排序但仅分区一次的数组：

[2, 3, 1, 4, 5, 7, 8, 6]

（也就是说，所有在数字 4 左边（右边）的元素都比它小（大）。）似乎递归调用 quicksort 并没有像调用 partition 那样在输入数组 A 上进行原地操作。我该如何解决这个问题？

- Kurt Peek

Answer 1

错误出在partition函数里，具体是在for j in range(p, r-1):这一行：应该改为for j in range(p, r):。

这种情况发生的原因是，在Python中，range函数的终止索引不包含在范围内，但是算法意味着要包括r-1，因此必须在r处停止以包括r-1。

- DjaouadNM