如何为 'quick Sort' 完成这些 python 功能？

Question

这两个函数可以协同工作以对整数数组进行排序。函数 quickSort 是完整的，如果 partition 函数被完整定义，它将正常工作。我不确定其余的功能应该是什么才能具有有效的功能。

def quickSort(mylist,start,end):
    if start<end:
        pivotpos = partition(mylist,start,end)
        print("pos",pivotpos)
        quickSort(mylist,start,pivotpos-1)
        print(quickSort(mylist,start,pivotpos-1))
        quickSort(mylist,pivotpos+1,end)
        print(quickSort(mylist,pivotpos+1,end))
def partition(mylist,left,right):
    pivot = mylist[left]
    pivotpos = left
    currentlow,currenthigh=left+1,right
    while currentlow<=currenthigh:
        if mylist[currentlow]<pivot:

        elif mylist[currentlow]==pivot: 

        else: 

    return pivotpos

partition 函数必须重新排列列表和 return 新的枢轴位置。

Answer 1

在配分函数中，你必须把mylist中小于pivot的每个元素都放在左边，而right的每个元素都放在左边.我们使用 currentlow 进行迭代，如果 mylist[currentlow] 小于 pivot 我们必须交换它们。在 currenthigh 变量中，我们保存了最后一个元素的位置，如果我们遇到一个大于枢轴的值，它将被交换。这样我们总是将大于 pivot 的元素放在列表的末尾。我希望你能理解下面的代码。

def quickSort(mylist, start, end):
    if start < end:
        pivotpos = partition(mylist, start, end)
        #print("pos", pivotpos)
        quickSort(mylist, start, pivotpos - 1)
        #print(quickSort(mylist, start, pivotpos - 1))
        quickSort(mylist, pivotpos + 1, end)
        #print(quickSort(mylist, pivotpos + 1, end))


def partition(mylist, left, right):
    pivot = mylist[left]
    pivotpos = left
    currentlow, currenthigh = left + 1, right
    while currentlow <= currenthigh:
        if mylist[currentlow] < pivot:
            mylist[currentlow], mylist[pivotpos] = mylist[pivotpos], mylist[currentlow]
            pivotpos = currentlow
        elif mylist[currentlow] > pivot:
            mylist[currentlow], mylist[currenthigh] = mylist[currenthigh], mylist[currentlow]
            currenthigh = currenthigh - 1
        currentlow = currentlow + 1
    return pivotpos

输出：

>>> from a import quickSort
>>> a = [3223,1,321,2,43,54,65,1]
>>> quickSort(a,0,7)
>>> a
[1, 1, 2, 43, 54, 65, 321, 3223]

如何为 'quick Sort' 完成这些 python 功能？

How to finish off these python functions for a 'quick Sort'?

python

sorting

quicksort