快速排序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

快速排序算法的小例子：

*

###  QUICKSORT
A=[44,5,22,0,323,995,94,4,7,15]
def main():
    r=len(A)-1
    p=0
    Result=QuickSort(A,p,r)
    print(Result)
def QuickSort(A,p,r):

    if p<r:
        q=partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)
    return A
def partition(A,p,r):
    x=A[r]
    i=p-1
    for j in range(p,r):
        if A[j]<=x:
            i=i+1
            a,b=A.index(A[i]), A.index(A[j])
            A[a],A[b]=A[b],A[a]
    d,c=A.index(A[i+1]),A.index(A[r])
    A[c],A[d]=A[d],A[c]
    return i+1
main()

*

Answer 2

我认为在纯递归实现中不需要分区辅助函数：

def quicksort_recursive(a):
    if len(a) == 0:
        return a
    p = len(a) // 2
    l = [i for i in a if i < a[p]]
    m = [i for i in a if i == a[p]]
    r = [i for i in a if i > a[p]]
    return quicksort_recursive(l) + m + quicksort_recursive(r)

Answer 3

您的代码中有许多问题，以下是一些为了使其正常工作而进行的修复：

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]