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

此实现给出了错误的输出。不对的地方指正一下。

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

快速排序 python 实现

quick sort python implementation

python

arrays

quicksort