能否实现签名为quicksort(arr)的原地递归快速排序？

完全可以实现签名为quicksort(arr)的原地无返回值快排函数，核心思路是用嵌套辅助函数处理递归所需的分区索引参数，对外只暴露接收数组的接口即可。

问题分析 #

你当前的quicksort函数依赖low和high参数，不符合作业要求的签名；同时函数最后返回了数组，而作业要求无返回值——其实列表是Python可变对象，原地修改会直接作用于原数组，完全不需要返回。

修改后的代码 #

import random

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):
    # 嵌套辅助函数处理递归的分区范围参数
    def _quicksort(arr, low, high):
        if high <= low:
            return
        # 随机选基准点，避免有序数组的最坏时间复杂度
        pivot_idx = random.randint(low, high)
        arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
        
        pivot = partition(arr, low, high)
        
        _quicksort(arr, pivot + 1, high)
        _quicksort(arr, low, pivot - 1)
    
    # 处理空数组或单元素数组的边界情况
    if len(arr) <= 1:
        return
    # 初始化递归范围为整个数组
    _quicksort(arr, 0, len(arr)-1)

关键修改点 #

• 新增嵌套的_quicksort辅助函数，保留原有的递归分区逻辑，专门处理low和high参数
• 对外的quicksort(arr)仅接收数组参数，内部先判断边界情况（数组长度≤1无需排序），再调用辅助函数初始化分区范围
• 移除原函数中return arr的语句，原地排序无需返回值，原数组会被直接修改
• 把round(random.random() * ...)替换为更可靠的random.randint(low, high)，避免浮点计算可能导致的索引错误

验证示例 #

test_arr = [3,1,4,1,5,9,2,6]
quicksort(test_arr)
print(test_arr)  # 输出: [1, 1, 2, 3, 4, 5, 6, 9]

内容的提问来源于stack exchange，提问作者Gabriel Denney-Martell