实现快速排序并得到一个我不理解的bug

Question

我有两个函数，一个函数划分数组和快速排序本身:

def partition(a, i, j):
    h = i+1
    for k in range(i+1, j):
        if a[k] < a[i]:
            a[h],a[k] = a[k],a[h]
            h += 1
    a[i],a[h-1] = a[h-1],a[i]
    return h 
# a is an array. After function call a[i..j-1] is sorted in increasing order
def quicksort(a, i, j):
    if j-i <= 1: return
    swap(a, i, j)
    p = partition(a, i, j)
    quicksort(a, i, p)
    quicksort(a, p, j)

这适用于我尝试过的所有测试用例，也就是说，我调用快速排序(a, 0, len(a))，列表a在后面排序。

我正在尝试更改pivot元素。我想使用数组的最后一个元素作为枢轴，而不是第一个元素(就像上面的实现一样)。为此，我在分区前的快速排序函数中添加了以下代码行:

a[i],a[j-1] = a[j-1],a[i]

，一切都坏了。超过最大递归深度。我不明白为什么会发生这样的事，我都快疯了。

Answer 1

给定输入[1,2,3]，它将陷入与p一致的无限循环;开关p与p-1/p+1:

def quicksort(a, i, j):
    if j <= i: return
    swap(a, i, j)
    p = partition(a, i, j)
    quicksort(a, i, p-1)
    quicksort(a, p+1, j)