快速排序python递归

Question

这是我的快速排序代码,该partition函数运行良好,但我在调用递归时遇到了问题.在pos每次启动该功能,然后将列表限制更改以及时间的变化.如何解决？

def partition(lst, start, end):

    pos=0
    if len(lst)<2:
        return 
    for i in range(len(lst[start:end])):
        if lst[i] < lst[end]:
            lst[i],lst[pos]=lst[pos],lst[i]
            pos+=1

        elif i==(len(lst[start:end])-1):
            lst[end],lst[pos]=lst[pos],lst[end]

    return pos

def quick_sort_recursive(lst, start, end):

        pos=partition(lst, start, end)
    if start<=pos<=end :
        quick_sort_recursive(lst, start, pos-1)
        quick_sort_recursive(lst, pos+1, end)
    else:
        return lst

Answer 1

您的代码中存在许多问题,以下是一些修复方法,只是为了使其工作:

def partition(lst, start, end):
    pos = start                           # condition was obsolete, loop won't
                                          # simply run for empty range

    for i in range(start, end):           # i must be between start and end-1
        if lst[i] < lst[end]:             # in your version it always goes from 0
            lst[i],lst[pos] = lst[pos],lst[i]
            pos += 1

    lst[pos],lst[end] = lst[end],lst[pos] # you forgot to put the pivot
                                          # back in its place
    return pos

def quick_sort_recursive(lst, start, end):
    if start < end:                       # this is enough to end recursion
        pos = partition(lst, start, end)
        quick_sort_recursive(lst, start, pos - 1)
        quick_sort_recursive(lst, pos + 1, end)
                                          # you don't need to return the list
                                          # it's modified in place

例:

example = [3,45,1,2,34]
quick_sort_recursive(example, 0, len(example) - 1)
print example

得到:

python test.py

[1,2,3,34,45]