我的快速排序挂起大小为 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 变得足够大以至于匹配端点很可能发生时，问题就出现了。

如果它有帮助，这里是我用来追踪问题的代码——它是你的，加上一些 print 插入和 indent 以帮助追踪通话深度。

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]

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

My quicksort hangs for list of size 2^13

python

stack-overflow

quicksort

tail-recursion