python中的快速排序- CLRS实现

Question

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

这是我写的。我认为，除了清单中的中间部分外，大多数情况下都很好。

有人能帮忙吗？

#! /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].Instead，它正在打印[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

而且效果很好。

Answer 2

使分区()变得更简单和Pythonic。

• 不需要交换()。
• 使用枚举()访问列表中的元素

def partition(A, p, r):
    pivot = A[r]
    i = -1
    for j, n in enumerate(A):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    return i