在Python中尝试快速排序算法时遇到了实现递归的问题

Question

我正在尝试用Python编写自己的快速排序算法，而没有查看它是如何专业地完成的（我将通过这种方式了解更多）。如果我打算如何实现这种快速排序的想法在您看来很愚蠢，（我知道它可能会）请不要给我一个完全不同的方法来实现它，除非我的方法永远不会成功，或者至少没有荒谬的措施，请帮我用我想要的方法达成解决方案：）

目前，我已经定义了一个函数“pivot”，它将获取输入列表并输出三个列表，一个比pivot小的数字列表（在本例中，每次都选择作为列表中的第一个数字），一个等于pivot的数字列表和一个比pivot大的数字列表

我的下一步是定义一个函数“q\u sort”。首先，此函数创建一个名为“finalList”的列表，并用0填充它，使其与正在排序的列表的长度相同。接下来，它旋转列表并将与轴相等的数字添加到finalList的正确位置（因为有0表示小于它的项目数，而0表示大于轴的项目数）

一切正常

下一步是做不好的。我已经在一些考虑不周的psuedo代码中写下了我接下来想要发生的事情：

numList = [3, 5, 3, 1, 12, 65, 2, 11, 32]

def pivot(aList):
    biggerNum =[]
    smallerNum = []
    equalNum = [aList[0]]
    for x in range(1, len(aList)):
        if aList[0]<aList[x]:
            biggerNum.append(aList[x])
        elif aList[0]>aList[x]:
            smallerNum.append(aList[x])
        elif aList[0] == aList[x]:
            equalNum.append(aList[x])
    pivoted = [smallerNum, equalNum, biggerNum]
    return pivoted

def q_sort(aList):
    finalList = []
    for x in range(len(aList)):
        finalList.append(0)
    pivot(aList)
    for i in range(len(pivot(aList)[1])):
        finalList[len(pivot(aList)[0])+i] = pivot(aList)[1][i]

伪代码：

    #if len(smallerNum) != 0:
        #q_sort(smallerNum) <--- I want this to add it's pivot to finalList
    #if len(biggerNum) != 0:
        #q_sort(biggerNum) <--- Again I want this to add it's pivot to finalList
#return finalList <--- Now after all the recursion every number has been pivoted and added

我打算做的是，如果小于pivot的数字列表中实际有任何项，那么它将对这个列表进行q\u排序。这意味着它将找到一个新的轴心，并将其值添加到finalList中的正确位置。我认为它的工作方式是，只有当“numList”中的每个数字都被放置在正确的位置时，函数才能到达“return finalList”。由于在q\u排序中包含q\u排序的递归性质意味着在透视“smallerNum”（并将透视添加到finalList）之后，它将有另一个要透视的列表

Answer 1

问题是每次通话都要从头开始：使用整个列表，从两端开始。您需要在列表的每个分区上重复：先是轴下面的部分，然后是轴上面的部分。这通常是通过传递子列表的端点来完成的，例如

def q_sort(aList, low, high):
    if low >= high:
        return

    # find pivot position, "pivot"
    ...
    # arrange list on either side of pivot
    ...
    # recur on each part of list. 
    q_sort(alist, low_index, pivot-1)
    q_sort(alist, pivot+1, high_index)

这足以让你动起来吗

如果没有，请尝试在“Python快速排序”上进行浏览器搜索，您会发现很多帮助，比我们在这里介绍的内容更全面