python - Quicksort - Python 中的 CLRS 实现

Question

我正在尝试在 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]。

Answer 1

根据我在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

而且效果很好。