python - 在Python中以最后一个元素为基准实现快速排序

Question

我似乎无法正确完成这项工作。我已将我的代码粘贴在下面。使用打印语句，我认为发生的情况是第一遍的结果就是作为答案返回的内容，尽管所有递归步骤都通过打印显示输出，表明它们正在按预期工作，但结果似乎没有被拯救吗？我试图就地执行此操作，我尝试这样做，但只是修改 array[]，但我觉得我在这里有一些误解。如有任何帮助，我们将不胜感激。

键盘:http://codepad.org/jVMbbJTq

代码:

def quicksort(array):
    if len(array) >1:
        print "enter array", array
        pivot = len(array) - 1
        print "pivot", array[pivot]
        x = 0
        while x < pivot:
            if array[x]>array[pivot]:
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
        #        temp = array[x]
         #       array[x] = array[pivot]
         #       array[pivot] = temp
               # array.append(array.pop(x))
                pivot -= 1
            else:
                x += 1
        print "pre recur split array", array
        print "left", array[:pivot]
        print "right", array[pivot+1:]
        quicksort(array[:pivot])
        quicksort(array[pivot+1:])
        print "post recur split array", array
    return array
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
#test = [21, 4, 1, 3]
print quicksort(test)
print "answer", test

Answer 1

我不确定这是否是您的代码的唯一问题，但您遇到的一个大问题是您的递归不会做任何有用的事情。也就是说，这两行对您没有任何作用:

    quicksort(array[:pivot])
    quicksort(array[pivot+1:])

它们不执行任何操作的原因是您执行的切片将数据从输入列表array复制到新列表中。然后递归调用尝试对复制的列表进行排序。递归排序根本不会更改原始列表，因此，如果您忽略它们的返回值，则调用代码中最终不会发生任何更改。

有几种方法可以解决此问题。一个简单(但效率低下)的修复方法是将每个递归调用返回的值分配回原始列表的切片中:

    array[:pivot] = quicksort(array[:pivot])
    array[pivot+1:] = quicksort(array[pivot+1:])

如果你打算做类似的事情，在代码前面的分区步骤中使用临时列表可能会让一切更容易理解(如果你要复制所有分区，就没有理由就地分区)无论如何在递归期间数据)。

这是一个非常快速但肮脏的快速排序，它会复制一堆东西(因此效率不是很高):

def quicksort(array):
    if len(array) <= 1:
        return array
    pivot_val = array[-1]
    lower = [x for x in array if x < pivot_val]
    upper = [x for x in array if x > pivot_val]
    pivot_count = array.count(pivot)
    return quicksort(lower) + [pivot_val]*pivot_count + quicksort(upper)

另一种更有效的方法是避免制作任何数据副本(这意味着不进行切片)。只需就地排序所有内容，包括递归部分。为此，您需要能够在递归调用中传递额外的参数来指定需要排序的索引范围。幸运的是，在 Python 中向函数添加可选参数很容易(另一个选择是使用一个单独的辅助函数来处理所有递归)。

与上面的简单修复相比，这涉及对代码的更多更改，因为您不能再使用 len(array) 作为应该找到枢轴的位置的指南(或告诉您何时'重新完成递归)。这是一个快速尝试，但我可能有一个 off by 1 错误或一些其他错误，您需要调试:

def quicksort(array, low=0, high=None):    # add optional arguments
    if high == None:
        high = len(array) - 1              # set high if it got the default
    if high - low > 0:
        pivot = high                       # use high and low to set up pivot and x
        x = low
        while x < pivot:
            if array[x]>array[pivot]:      # this part stays the same
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
                pivot -= 1
            else:
                x += 1
        quicksort(array, low, pivot-1)     # pass on new high and low values
        quicksort(array, pivot+1, high)
    return array                           # you probably don't need this line any more

如果您采用这种就地方法，您可能需要删除函数的返回数组部分。就地操作的 Python 函数的标准是返回 None(如果没有任何 return 语句，就会发生这种情况)。您熟悉的许多方法都是这样工作的。例如，list.append 不会返回任何内容，list.sort(“官方”排序函数)也不会返回任何内容。标准库模块中的函数(例如 random.shuffle)在修改您传递给它们的列表时也将返回 None。