2

我很难理解为什么我的 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]

先感谢您！

4

4 回答 4

1

这是因为您在return声明中编制了一个新列表。

return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

如果qSort函数到达基本情况，它会返回一个列表，该列表与 . 连接[p_value]并返回为list. 您不会在list任何地方对传入的内容进行更改。

当你qSort递归调用你的函数时，你给它一个列表的一部分，函数返回基本情况下的列表，然后你将其附加到pivot另一个递归调用，从而生成一个新列表。

通过将您的qSort功能更改为

def qSort(array):
    n = len(array)
    if (n == 1 or n ==0):
            return array
    p_index, array = partition(array)
    p_value = array[p_index]
    returnVal = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])
    print "Returning:", returnVal, "Original Array:", array
    return returnVal

输出 -

>>> q = [5,4,3,2,1]
>>> qSort(q)
Returning: [2, 3] Original Array: [2, 3]
Returning: [2, 3, 4] Original Array: [2, 3, 4]
Returning: [1, 2, 3, 4] Original Array: [1, 4, 3, 2]
Returning: [1, 2, 3, 4, 5] Original Array: [1, 4, 3, 2, 5]
[1, 2, 3, 4, 5]

要反映您原来的更改list，您可以选择这样做q = qSort(q)。

PS - 设置一个随机索引而不是第一个值对于您的快速排序功能会更好。请参阅此处的位Choice of Pivots。

于 2013-07-20T08:07:28.397 回答
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))对数组进行排序。

于 2013-07-20T08:23:39.180 回答
0

将函数应用回 q

q = qSort(q)

于 2013-07-20T08:08:49.663 回答
0

如果你想返回数组并在原地排序，你应该在返回之前使数组等于结果而不是创建一个新数组。您可以通过将您的 return 语句更改为：

    array[:] = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])
    return array

注意

    array = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])

也不起作用，因为 lhs 变量将被视为局部变量。

于 2013-10-08T13:21:23.630 回答