就地快速排序 - python

Question

我正在尝试就地在python中实现快速排序。我在这里遵循了维基百科文章中的伪代码，但这并没有产生排序列表。有什么明显不对劲的地方吗？

# Perform QuickSort in place
def partition(arr,low,high):
    pivotIndex = random.randint(0,high)
    pivotValue = arr[pivotIndex]
    currentIndex = low
    t = arr[high]
    arr[high] = pivotValue
    arr[pivotIndex] = t
    for i in range(low,high-1):
        if arr[i] < pivotValue:
            t = arr[i]
            arr[i] = arr[currentIndex]
            arr[currentIndex] = t
            currentIndex += 1
    t = arr[currentIndex]
    arr[currentIndex] = arr[high]
    arr[high] = t
    return currentIndex
def quickSort(arr,low,high):
    # pick partition
    if low < high:
        part = partition(arr,low,high)
        quickSort(arr,low,part-1)
        quickSort(arr,part+1,high)
arr = [1,3,6,7,9,10]
quickSort(arr,0,len(arr)-1)
print arr

Answer 1

好吧，partition函数的第一行显然是错误的：

pivotIndex = random.randint(0, high)

这显然应该是low而不是0.

您的range值可能已关闭...我认为您不需要从high中减去 1

Answer 2

此外，在 Python 中，您不必使用临时变量来进行交换。

而不是：

t = x
x = y
y = t

你可以做：

x, y = y, x

Answer 3

你记得import random吗？此外，为了看到差异，您的数组必须是未排序的数组。如果元素的顺序已经正确，如何找到差异？

此外，将所有数组列为 arr ，可能会令人困惑。我注意到所有带有 arr 的函数都使用 arr 作为相应的参数。为什么不做一些事情来区分它们呢？