Python快速排序（QuickSort）实现问题：返回顺序不正确

你的问题出在递归调用时使用了列表切片：nums[:pointer]和nums[pointer+1:]会生成原列表的副本，递归函数里排序的是这些副本，完全不会修改原列表的对应子数组，所以递归返回后，原数组的子部分还是初始状态，看起来像是元素被换回了原位置。

修正方案 #

要解决这个问题，需要让递归排序的结果作用于原数组，有两个关键修改：

1. 修正base case：当数组长度≤1时，直接返回原数组（无需排序），确保递归调用能返回排序后的子数组。
2. 将递归排序后的子数组重新赋值回原数组的对应切片位置。

修正后的完整代码 #

def sortArray(self, nums: List[int]) -> List[int]:
    # quick sort implementation
    if len(nums) <= 1:
        return nums
    
    pivot = nums[-1]
    pointer = 0
    iter_pointer = 0

    while iter_pointer < len(nums) - 1:                
        if nums[iter_pointer] <= pivot:
            temp = nums[iter_pointer]
            nums[iter_pointer] = nums[pointer]
            nums[pointer] = temp
            pointer += 1
        
        iter_pointer += 1
    
    # put pivot in middle
    nums[-1] = nums[pointer]
    nums[pointer] = pivot

    # 将排序后的子数组赋值回原数组对应位置
    nums[:pointer] = self.sortArray(nums[:pointer])
    nums[pointer + 1:] = self.sortArray(nums[pointer + 1:])

    return nums

为什么原代码无效？ #

列表切片nums[a:b]是创建原列表的新副本，递归函数中对这个副本的任何修改都不会同步到原列表。比如你对nums[:pointer]排序，只是修改了那个临时副本，原列表的前pointer个元素根本没变化，所以递归返回后看起来元素被还原了。

内容的提问来源于stack exchange，提问作者Joseph