快速排序的这种实现有什么问题？

Question

我试图实现快速排序算法，选择pivot作为最右边的元素，如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)

但是，如果我试着这样测试：

^{pr2}$

我得到一个数组，它不排序，但只分区一次：

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

（也就是说，4的左（右）元素都比它小（大）。似乎对quicksort的递归调用并不像对partition的调用那样在输入数组A上操作到位。我该怎么解决这个问题？在

Answer 1

错误在partition，正好在for j in range(p, r-1):： 它必须是for j in range(p, r):。

这是因为在Python中，停止索引不包括在范围内，但是算法意味着包含r-1，因此必须在r处停下来才能包含r-1。在