python中的快速排序实现

Question

我正在尝试编写一个快速的就地排序函数，下面是我的代码

def quick_sort(ar):
    if len(ar) < 2:
        return ar
    pivot = ar[-1]
    i = 0

    for j in range(len(ar)):
        if ar[j] < pivot:
            ar[i], ar[j] = ar[j] , ar[i]
            i += 1
    ar[i], ar[-1] = ar[-1], ar[i]

    quick_sort(ar[0:i])
    quick_sort(ar[i+1:])

    return ar


lst = [1, 3, 9, 8, 2, 7, 5]
print quick_sort(lst)

但是我得到了一个空的列表..我在这里错过了什么？

Answer 1

您的递归调用是在列表的片段上进行的。切片会产生一个副本，所以递归根本不会改变原始列表。您要么需要使用递归调用的返回值，要么应该就地执行所有操作。其中每一项都需要在不同的位置对代码进行一些更改

以下是构建新列表的代码版本：

def quick_sort(ar):
    if len(ar) < 2:
        return ar
    pivot = ar[-1]
    i = 0

    for j in range(len(ar)):
        if ar[j] < pivot:
            ar[i], ar[j] = ar[j] , ar[i]
            i += 1
    ar[i], ar[-1] = ar[-1], ar[i]

    result = quick_sort(ar[0:i]) # build a new result list from the recursive calls
    result.append(pivot)
    result.extend(quick_sort(ar[i+1:]))

    return result

这是一个就地排序的方法：

def quick_sort(ar, low=0, high=None):   # get sorting bounds as arguments
    if high is None:
        high = len(ar)
    if high - low < 2:
        return
    pivot = ar[high-1]
    i = low

    for j in range(low, high):   # iterate on a limited range
        if ar[j] < pivot:
            ar[i], ar[j] = ar[j] , ar[i]
            i += 1
    ar[i], ar[high-1] = ar[high-1], ar[i]

    quick_sort(ar, low, i)
    quick_sort(ar, i+1, high)

    # no need to return anything, since we sorted ar in place

考虑到您如何进行分区，就地版本可能更有意义。如果将另一个版本与使其成为稳定排序的分区方案配对，则会更有趣(没有简单的方法可以就地进行稳定的快速排序)。