python - 使用就地排序的 QuickSort

Question

我正在尝试使用就地排序在 python 中编写快速排序代码。我的代码在子数组中运行完美，但是它似乎无法将子数组粘在一起以形成最终的排序数组。

def quickSort (ar):

    if len(ar)>1:
        pivot = ar[-1]
        wall = 0
        for i in range(len(ar)-2):
            if ar[i] <= pivot:
                ar[wall], ar[i] = ar[i], ar[wall]
                wall += 1
        ar[wall], ar[-1] = ar[-1], ar[wall]
        quickSort (ar[:wall])
        quickSort (ar[wall+1:])

Answer 1

您的代码尝试就地排序，但随后它将切片副本传递给递归调用，因此您只需就地对这些副本进行排序，然后丢弃它们。

(如果不清楚:对列表进行切片总是复制列表。更复杂的类型 - 例如 memoryview 或 np.array - 可能支持对其部分结构的“共享 View ”，但列表故意简单。)

<小时/>

解决此问题的一种方法是更改​​为复制而不是就地排序，其结尾为:

return quickSort(ar[:wall]) + ar[wall] + quickSort(ar[wall+1:])

(当然，您还需要更改上面的简单代码以构建副本而不是就地洗牌。)

<小时/>

另一种方法是通过传递列表本身和切片索引来继续就地执行此操作，而不是列表的切片副本:

def quickSort(ar, start=None, stop=None):
    if start is None: start = 0
    if stop is None: stop = len(ar)

    pivot = ar[stop-1]
    for i in range(start, (stop-start)-2):

    # and so on

    quickSort(ar, start, wall)
    quickSort(ar, wall+1, stop)

<小时/>

只要确保您选择其中一个即可 - 一种部分就地、部分复制和组装的类型是一团糟。