python - QuickSort 返回正确的值，但未就地排序

Question

我很难理解为什么我的 QuickSort返回正确的排序值，但结果数组排序不正确。

def qSort(array):
    n = len(array)
    if (n == 1 or n ==0):
            return array
    p_index = partition(array)
    p_value = array[p_index]
    return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

def partition(array):
    pivot = array[0]
    i = 1
    for j in xrange(1,len(array)):
        print j
        if array[j] < pivot:
            tmp = array[j]
            array[j] = array[i]
            array[i]=tmp
            i += 1
    tmp = array[i-1]
    array[i-1] = pivot
    array[0] = tmp
    return i-1

这是一些示例输出:

>>> q = [5,4,3,2,1]
>>> qSort(q)
[1, 2, 3, 4, 5]
>>> q
[1, 4, 3, 2, 5]

提前谢谢您!

Answer 1

在 Python 中，切片和组合列表会创建新列表。如果您希望递归调用在单个列表上进行操作，请将列表和边界传递到调用中，并且不要从函数返回任何内容。像这样的东西:

def qsort(array, low, high):
    if high-low < 2:
        return

    # Choose pivot, do partition within bounds

    if partition > low:
        qsort(array, low, partition)
    if partition < high:
        qsort(array, partition+1, high)

然后只需调用 qsort(a, 0, len(a)) 对数组进行排序。