Python 中的就地快速排序

我必须用我选择的语言来实现作业的快速排序算法，所以我选择了 Python。

在讲座中，我们被告知 QuickSort 内存效率高，因为它就地工作；即，它没有用于递归的输入数组部分的额外副本。

考虑到这一点，我尝试在 Python 中实现 QuickSort 算法，但不久之后意识到，为了编写一段优雅的代码，我必须在递归时将数组的一部分传递给函数本身。由于每次执行此操作时 Python 都会创建新列表，因此我尝试使用 Python3（因为它支持 nonlocal 关键字）。以下是我的注释代码。

def quicksort2(array):
# Create a local copy of array.
arr = array

    def sort(start, end):
        # Base case condition
        if not start < end:
            return

        # Make it known to the inner function that we will work on arr
        # from the outer definition
        nonlocal arr

        i = start + 1
        j = start + 1

        # Choosing the pivot as the first element of the working part
        # part of arr
        pivot = arr[start]

        # Start partitioning
        while j <= end:
            if arr[j] < pivot:
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
                i += 1
            j += 1
        temp = arr[start]
        arr[start] = arr[i - 1]
        arr[i - 1] = temp
        # End partitioning

        # Finally recurse on both partitions
        sort(start + 0, i - 2)
        sort(i, end)
    sort(0, len(array) - 1)

现在，我不确定我是否完成了这项工作，或者我是否遗漏了一些东西。我编写了一个更Pythonic 的QuickSort 版本，但这肯定不能就地工作，因为它不断返回输入数组的一部分并将它们连接起来。

我的问题是，这是Python 中的做法吗？我已经搜索了 Google 和 SO，但还没有找到 QuickSort 的真正就地实现，所以我认为最好询问一下。

当然不是最好的方法，加上这个著名的算法将有几十个完美的实现..这是我的，很容易理解

def sub_partition(array, start, end, idx_pivot):

    'returns the position where the pivot winds up'

    if not (start <= idx_pivot <= end):
        raise ValueError('idx pivot must be between start and end')

    array[start], array[idx_pivot] = array[idx_pivot], array[start]
    pivot = array[start]
    i = start + 1
    j = start + 1

    while j <= end:
        if array[j] <= pivot:
            array[j], array[i] = array[i], array[j]
            i += 1
        j += 1

    array[start], array[i - 1] = array[i - 1], array[start]
    return i - 1

def quicksort(array, start=0, end=None):

    if end is None:
        end = len(array) - 1

    if end - start < 1:
        return

    idx_pivot = random.randint(start, end)
    i = sub_partition(array, start, end, idx_pivot)
    #print array, i, idx_pivot
    quicksort(array, start, i - 1)
    quicksort(array, i + 1, end)

好的，首先是分区子例程的单独函数。它需要数组， 兴趣点的起点和终点，以及枢轴索引。这个功能应该很清楚

然后快速排序对整个数组第一次调用分区子例程；然后 递归地调用自身来对枢轴之前的所有内容以及之后的所有内容进行排序。

如果你不明白什么就问