这种快速排序的实现是否被视为“就地”？

Question

这是一种快速排序的实现，比我发现的其他方法更容易理解。尽管此实现似乎没有“就位”，但显然应该进行快速排序。我认为它不在“原地”，因为您要返回一个新数组。

我是否认为此实现未“到位”？

def quick_sort(sequence):
    length = len(sequence)
    if length <= 1:
        return sequence
    else:
        pivot = sequence.pop()

    items_greater = []
    items_lower = []

    for item in sequence:
        if item > pivot:
            items_greater.append(item)
        else:
            items_lower.append(item)

    return quick_sort(items_lower) + [pivot] + quick_sort(items_greater)

这是我发现的另一个实现，我认为它是快速排序的“就地”版本。 -> https://stackabuse.com/quicksort-in-python/

[如果有人可以确认这一点。我会很感激。谢谢！

Answer 1

不，它不是快速排序算法的“就地”实现。

此实现较容易掌握，但效率很低。请记住，对于您要排序的数组，它会创建一个大小相同的新数组，然后为一半数组创建另一个数组，然后为一半数组或另一个数组，依此类推。 ..您将为大型数组浪费大量内存。

Answer 2

肯定是not-您正在生成新的数组（items_lower等）