快速排序，第一次排序有效，递归调用的参数不

Question

我想编写自己的快速排序（我是一名初级程序员，我知道我可以在网上查找它，重点是让我在给出宽松描述的情况下变得更好）

它在第一次迭代时排序，但不幸的是我无法为递归调用获取正确的参数。我想我需要 2 个递归调用，一个用于左侧，一个用于我的枢轴元素新位置的右侧。

我知道选择更好的主元可以更好地完成快速排序，我只是选择了列表的第一个元素。

def qt(alist,l,r):
    if l != r:
        x=l+1
        run=l+1
        while run<r:            
            if alist[l]>alist[run]:
                alist[x],alist[run]=alist[run],alist[x]
                x=x+1
                run=run+1

            else :
                run=run+1
        alist[x],alist[l]=alist[l],alist[x]
        #qt(alist,0,x-1)
        #qt(alist,x+1,r)

clist = [54,26,93,17,77,31,44,55,20,104,3,5,123,423423,9]
l=0
r=len(clist)
qt(clist,l,r)
print clist

Answer 1

为清楚起见，我将重命名一些内容（我建议您也这样做）：

def quickSort(aList, l, r):
    if l < r:
        swap = l
        run = l
        pivot = aList[r]
        while run < r:            
            if pivot >= aList[run]:
                aList[swap],aList[run]=aList[run],aList[swap]
                swap += 1
            run += 1

        aList[swap], aList[r] = aList[r], aList[swap]
        quickSort(aList, l, swap-1)
        quickSort(aList, swap+1, r)

您的 swap 值 (a.k.a x) 可能应该包含在内；虽然如果你想写一个排他性的 (left, right) 你可以，但是，它会违背普遍接受的 [left, right] 或 [left, right].

试一试： https://repl.it/BVTx/1

Answer 2

你的下标确实不对。您必须使它们与 Python 的基于 0 的索引保持一致。修复这个将修复你的无限递归如果你在开始时将它与'less than'检查结合起来。

另外，你的逻辑有一点小错误；您的 x 值可以运行超出范围。这是我对您的代码的更新，以解决第一个问题；在标准调试打印语句的帮助下，我会将内部逻辑留给您。就在失败点之前，我们得到 l=13, x=r=15.

的下标

def qt(alist, l, r):
    print "ENTER", alist, l, r
    if l < r:
        x = l+1
        for run in range(l+1, r):
            if alist[l] > alist[run]:
                alist[x], alist[run] = alist[run], alist[x]
                x += 1

        print "subscripts", l, x, r
        alist[x], alist[l] = alist[l], alist[x]
        qt(alist, l, x-1)
        qt(alist, x+1, r)
    print "LEAVE", alist, l, r

clist = [54,26,93,17,77,31,44,55,20,104,3,5,123,423423,9]
l=0
r=len(clist)
qt(clist,l,r)
print clist

快速排序，第一次排序有效，递归调用的参数不

quick sort, first sort works, parameters for recursive calls don't

python

quicksort