python - 就地快速排序实现

Question

我正在尝试按照 http://en.wikipedia.org/wiki/Quicksort 中的说明实现就地快速排序

下面是 python 代码，分区函数没有按预期工作。

def swap(array, index1, index2):
    tmp = array[index1]
    array[index1] = array[index2]
    array[index2] = tmp

def partition(array, left, right, pivotIndex):
    pivotValue = array[pivotIndex]
    swap(array, pivotIndex, right)
    storeIndex = left
    for i in range(left, right - 1):
        if array[i] < pivotValue:
            swap(array, i, storeIndex)
            storeIndex = storeIndex + 1
            print array, i
    swap(array, storeIndex, right)
    return storeIndex

def quicksort(array, left ,right):
    if right > left:
        print left, right
        pivotIndex = left
        pivotNewIndex = partition(array, left, right, pivotIndex)
        quicksort(array, left, pivotNewIndex - 1)
        quicksort(array, pivotNewIndex + 1, right)

if __name__ == '__main__':
    array = [3,7,8,5,2,1,9,5,4]
    partition(array, 0, len(array) - 1, 3) # 5 is pivot
    print array # expecting all the elements to the left of pivot value(5) will be lesser or equal.

Answer 1

您至少需要进行 2 次修复:

def partition(array, left, right, pivotIndex):
    pivotValue = array[pivotIndex]
    swap(array, pivotIndex, right)
    storeIndex = left
    for i in range(left, right):    # range doesn't include right element already
        if array[i] <= pivotValue:  # need to check for equality (not really necessary for the sorting routine)
            swap(array, i, storeIndex)
            storeIndex = storeIndex + 1
            print array, i
    swap(array, storeIndex, right)
    return storeIndex

range(left, right)返回这样的项目列表 [left, left + 1, ..., right - 1] , 因此无需使用 range(left, right -1) 生成列表，因为这样我们不仅要跳过列表的最后一个元素(pivot 所在的位置)，还要跳过最后一个元素(即 right - 2 )。

如果预计在partition之后pivot 左边的元素应该小于或等于，我们应该在数组遍历(array[i] <= pivotValue)的比较中反射(reflect)它。