如何完成这些python函数的“快速排序”?

2024-03-29 06:25:23 发布

您现在位置:Python中文网/ 问答频道 /正文

这两个函数可以一起对整数数组进行排序。函数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函数必须重新排列列表并返回新的轴心位置。你知道吗


Tags: 函数功能rightifdefleftstartend
1条回答
网友
1楼 · 发布于 2024-03-29 06:25:23

在配分函数中,必须把mylist中小于pivot的每个元素放在左边,把大于right的每个元素放在左边。我们使用currentlow进行迭代,如果mylist[currentlow]小于pivot,我们必须交换它们。在currenthigh变量中,我们保存最后一个元素的位置,如果我们遇到一个比pivot大的值,它将被交换。这样,我们总是将大于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]

相关问题 更多 >