如何使这种快速排序实现工作？

Question

我是C++开发人员，是新的Python。我想用python实现快速排序，下面是我的代码：

from typing import Sequence, MutableSequence

def find_if(list: Sequence, predicate):
    """Find first element of the list which predicate return true"""
    for i in range(len(list)):
        if predicate(list[i]):
            return i
    return None

def find_if_not(list: Sequence, predicate):
    return find_if(list, lambda x : not predicate(x))

def partition(list: MutableSequence, predicate):
    """Reorder elements in list in such away that all element which the predicate
    return `true` precede the elements for which predicate returns false. Return
    value is index of the first element in the second group"""
    first = find_if_not(list, predicate)
    if first == None:
        return first

    for i in range(first+1, len(list)):
        if predicate(list[i]):
            list[i], list[first] = list[first], list[i]
            first = first + 1

    return first

def quick_sort(list: MutableSequence, key = lambda x : x):
    if len(list) <= 1:
        return

    pivot = list[0]
    last1 = partition(list, lambda x : x < pivot)
    first2 = partition(list[last1:], lambda  x : x == pivot)

    quick_sort(list[0:last1])
    if first2:
        quick_sort(list[first2:])

if __name__ == '__main__':
    arr = [6, 4, 7, 2, 8, 1, 3, 5, 2, 10, 13, 124, 1, 7]
    result = sorted(arr)
    quick_sort(arr)
    print("My sorted array: ", arr)
    print("Corrected result: ", result)

结果不正确。我认为问题是list[0:last1]和list[first2:]复制而不是引用列表中的元素。我怎样才能做到这一点？（我不想将索引范围作为quick_sort的参数或使用非递归算法。）

Answer 1

正确-列表切片，在python中是这样调用的，它在原始切片处返回原始列表的副本。就快速排序而言，最简单的解决方案是简单地使用列表连接。返回排序后的列表，而不是从快速排序返回None。然后，将左列表和右列表连接起来，使轴心位于它们之间：

def quick_sort(list: MutableSequence, key = lambda x : x):
    if len(list) <= 1:
        return list

    ...

    return quick_sort(list[:last1]) + [pivot] + quick_sort(list[first2:])

请注意，quick_sort在提供空列表时将返回空列表，因此在本例中不需要if语句。这可能是您在使用快速排序时要采用的方法—python的许多字符串操作和列表操作都是非变异的，my_list = quick_sort(my_list)与my_list.sort()一样清晰，而且能够创建列表的排序副本而无需更改列表。你知道吗