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

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)

您的交换值(又名x)可能应该包含在内；虽然如果你想写一个排他的(左，右)你可以，但是，它会违背普遍接受的[左，右]或[左，右]的原则。

尝试一下: https://repl.it/BVTx/1