python之Quicksort之Python 中的 CLRS 实现

我正在尝试在 python 中实现快速排序。 CLRS算法版本。

这是我写的。我认为除了列表的中间元素外，它在大多数情况下都运行良好。

有人可以帮忙吗？

#! /usr/bin/python 
 
#quick sort 
 
def swap(array,i,j): 
    temp = array[i] 
    array[i] = array[j] 
    array[j] = temp 
 
def partition(array, start,end): 
    x = array[end] 
    i = start -1 
    for j in xrange(start+1, end): 
        if (array[j] <= x): 
            i = i+1 
            swap (array,i,j) 
        swap(array,i+1,end) 
    return i+1 
 
def quicksort(array,p,r): 
    if p<r: 
        q = partition(array,p,r) 
        quicksort(array,p,q-1) 
        quicksort(array,q+1,r) 
 
def main(): 
    unsortedArray = [2,8,7,1,3,5,6,4,9,0] 
    quicksort(unsortedArray,0,len(unsortedArray)-1) 
    print unsortedArray 
 
 
if __name__ == '__main__': 
    main() 

输出应该是 [0,1,2,3,4,5,6,7,8,9]。而是打印 [2, 0, 3, 4, 1, 6, 5, 7, 9, 8]。

请您参考如下方法:

根据我在https://users.cs.fiu.edu/~giri/teach/5407/F08/Lec7.pdf上找到的伪代码, 您对 partition 的实现是错误的，因为

swap(array,i+1,end) 

不应不在每次迭代中执行，而是在函数中只执行一次。

我改写成这样:

def partition(array, start,end): 
    x = array[end] 
    i = start -1 
    for j in xrange(start, end): 
        if (array[j] <= x): 
            i = i+1 
            swap (array,i,j) 
    swap(array,i+1, end) 
    return i+1 

而且效果很好。