Python快速排序异常：输入数组元素被错误替换为相同值的原因排查

错误根源 #

在partition函数的最后一步，你写了nums[i+1], pivot = pivot, nums[i+1]，这是核心错误：

• pivot只是nums[end]的一个值副本，不是数组的引用。修改这个变量只会改变pivot自身的值，完全不会影响原数组中nums[end]位置的元素。
• 举个例子，第一次处理[4,2,6,3]时，基准值pivot是3，循环结束后i=1。执行这行代码后，nums[2]被改成3，但nums[3]还是原来的3，而原本在nums[2]的6被存到了pivot变量里，根本没回到数组中，直接导致元素丢失、重复，后续递归排序自然会彻底出错。

修复方法 #

把错误的交换代码替换成交换数组中的基准元素到正确位置——基准值原本在end位置，我们需要把它放到分割点i+1的位置：

nums[i+1], nums[end] = nums[end], nums[i+1]

修正后的完整代码 #

def partition(nums, start=0, end=None):
    if end is None:
        end = len(nums)-1

    i, j, pivot = start-1, start, nums[end]

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

    # 修正：将基准元素从end位置移到分割点
    nums[i+1], nums[end] = nums[end], nums[i+1]
    return i+1

def quicksort(nums, start=0, end=None):
    if end is None:
        end = len(nums) - 1

    # 优化：start >= end时无需递归，减少无效调用
    if start < end:
        pivot_idx = partition(nums, start, end)
        quicksort(nums, start, pivot_idx-1)
        quicksort(nums, pivot_idx+1, end)

    return nums

测试输入[4,2,6,3]，运行后会得到正确结果[2,3,4,6]。

内容的提问来源于stack exchange，提问作者scooby-doo