python - 快速排序python实现

Question

def quicksort(a,start,end):
    if(start<end):
        #print(start,end)
        p_index = partition(a,start,end)
        quicksort(a,start,p_index-1)
        quicksort(a,p_index+1,end)

def partition(a,start,end):
    pivot = a[end]
    pindex = start
    for i in range(start,end):
        if (a[i]<= pivot):
            a[pindex],a[i]=a[i],a[pindex]
            pindex = pindex+1
    a[pindex],a[pivot]=a[pivot],a[pindex]
    print(pindex)
    return pindex

a = [7,6,5,0]
quicksort(a,0,3)
print(a)

这个实现给出了错误的输出。纠正我做错的地方。

标签： pythonarraysquicksort

Answer 1

partition函数中将枢轴元素交换到其最终位置的行不正确。pivot是枢轴元素的值，而不是它的索引。那时枢轴的索引仍然是end。

改变：

a[pindex],a[pivot]=a[pivot],a[pindex]

至：

a[pindex],a[end]=a[end],a[pindex]

或者可能：

a[end] = a[pindex]  # we don't need to do a simultaneous swap because we already
a[pindex] = pivot   # have a separate reference to the value of the pivot element