在Python中编写快速排序时，是否可以同时具有quicksort(arr) -> void的方法签名，并且让快速排序递归？

Question

我已经为数据结构类编写了一个作业，并且无法弄清楚如何“实现对分区形成的子数组进行递归排序的主快速排序函数”，这意味着递归发生在主快速排序函数中，同时也“[具有] 方法签名：quicksort(arr) — 对列表 arr 就地排序并且不返回任何内容”

我正在努力想知道如何在不做愚蠢的事情的情况下将其实现到作业中。助教是一个非常非常严格的标记者，需要一切都严格按照作业的要求（即使是作业或幻灯片中没有明确说明的事情）。我所要求的只是我所问的问题在技术上是否可行。

现在，我有以下内容：

def partition(arr, low, high):
    pivot = arr[high]
    pivIndex = high
    while True:
        while arr[low] <= pivot and low != high:
            low += 1
        while arr[high] >= pivot and low != high:
            high -= 1
        if low == high:
            arr[low], arr[pivIndex] = arr[pivIndex], arr[low]
            return low
        else:
            arr[low], arr[high] = arr[high], arr[low]
            
def quicksort(arr, low, high):
    #the subarray has strictly less than two elements
    if high <= low:
        return

    pivot = round(random.random() * (high - low) + low)

    arr[pivot], arr[high] = arr[high], arr[pivot]

    pivot = partition(arr, low, high)

    quicksort(arr, pivot + 1, high)
    quicksort(arr, low, pivot - 1)

    return arr

Answer 1

尝试实现辅助函数并在主快速排序（arr）函数中递归调用它

类似这样的：

def quicksort(arr):

    def partition(low, high):
        ...

    def quicksort_recursive(low, high):

        if high <= low:
            return

        pivot = round(random.random() * (high - low) + low)
        arr[pivot], arr[high] = arr[high], arr[pivot]
        
        pivot = partition(low, high)
        
        quicksort_recursive(low, pivot - 1)
        quicksort_recursive(pivot + 1, high)


    quicksort_recursive(0, len(arr) - 1)

Python 中的列表是可变的，因此如果就地更改它，则无需从函数返回 arr