python - 我的快速排序因大小为 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

是的，你的逻辑有问题。如果 partition 收到一个子列表，其中 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]