快速排序 - 在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]。

- shobhit1

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

它可以正常工作。

- gefei

Answer 2

使 partition() 更简单和 Pythonic。

• 不需要 swap()。
• 使用 enumerate() 访问列表中的元素

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

- user