时间戳

首页 > 解决方案 > 使用就地排序的快速排序

python - 使用就地排序的快速排序

问题描述

我正在尝试使用就地排序在 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:])

标签： pythonpython-3.xquicksort

解决方案

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

（如果不清楚：对列表进行切片总是会复制列表。更复杂的类型（如memoryview或np.array）可能在其部分结构上支持“共享视图”，但列表故意简单。）

解决此问题的一种方法是更改​​为复制而不是就地排序，这可以以以下方式结束：

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)

只要确保你选择一个或另一个 - 一种部分就地并且部分复制和组装的类型是一团糟。

推荐阅读