python - 这个快速排序的实现有什么问题？

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 上运行。我该如何解决这个问题？

Answer 1

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

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