我的快速排序挂起2^13大小的列表

Question

我用python编写了一个快速排序函数，如下所示

def quickSort1(A,p,q):
    if p < q:
        pivotIndex = partition(A,p,q)
        quickSort1(A,p,pivotIndex-1)
        quickSort1(A,pivotIndex+1,q)
def partition(A,first, last):
    pivot = A[first]
    tooBig = first+1
    tooSmall = last
    while True:
        while tooBig<=last and A[tooBig]<pivot:
            tooBig+=1
        while tooSmall>first and A[tooSmall]>pivot:
            tooSmall-=1
        if tooBig < tooSmall:
            temp = A[tooBig]
            A[tooBig] = A[tooSmall]
            A[tooSmall] = temp
        else:
            break
    A[first] = A[tooSmall]
    A[tooSmall] = pivot
    return tooSmall

我正在用不同大小的列表（从2到2^16）测试算法的执行时间。例如

n = 2**13
s = [random.randint(-65536,65536) for i in range(n)]
#Begin Regular Quick Sort test with unsorted list
setup = '''
gc.enable()
from __main__ import quickSort1
from __main__ import n
from __main__ import s
            '''
 average = sum(timeit.Timer('A=s[:]; quickSort1(A,0,len(A)-1)',setup = setup).repeat(1,10))/10

我已经验证了该算法对于较小的尺寸是正确的，但是一旦我达到2^13，程序就会挂起。我试过做sys.setrecursionlimit(2**30)，但这并没有改变任何事情。我的算法有问题吗

Answer 1

是的，你的逻辑有错误。如果分区收到一个子列表，其中a[tooBig]==a[tooSmall]，那么while循环条件从一开始就是False，而If交换相等的值。什么都没变，你被困在一个无限循环中

我已经设法用212重现了这个问题：当你的**n变得足够大以至于很可能出现匹配的端点时，问题就出现了

如果有帮助的话，这是我用来追踪问题的代码，这都是你的代码，有一些打印插入和缩进帮助追踪调用深度

indent = ""

def quickSort1(A,p,q):
    global indent
    print indent, "ENTER", p, q
    indent += "  "

    if p < q:
        pivotIndex = partition(A,p,q)
        quickSort1(A,p,pivotIndex-1)
        quickSort1(A,pivotIndex+1,q)
    indent = indent[2:]
    print indent, "LEAVE"


def partition(A,first, last):
    print indent, "  PART", first, last
    pivot = A[first]
    tooBig = first+1
    tooSmall = last
    while True:
        if abs(tooSmall-tooBig) < 10:
            print indent, tooSmall, tooBig, A[tooBig:tooSmall+1]
        while tooBig<=last and A[tooBig]<pivot:
            tooBig+=1
        while tooSmall>first and A[tooSmall]>pivot:
            tooSmall-=1
        if tooBig < tooSmall:
            temp = A[tooBig]
            A[tooBig] = A[tooSmall]
            A[tooSmall] = temp
        else:
            break
    A[first] = A[tooSmall]
    A[tooSmall] = pivot
    print indent, "  PART", tooSmall
    return tooSmall

最常见的循环是当列表降到两个相等的值时。这里有一个较长的：

2030 2022 [-32421, -32303, -32723, -32402, -32705, -32269, -32422, -32834, -32421]