为何Python快速排序中赋值交换与swap函数交换结果不同？

错误的快速排序代码 #

def partion(arr,low,high):
    partion_index=low
    pivot=arr[partion_index]

    while (low < high):
        while low < len(arr) and (arr[low]<=pivot):
            low+=1
        while (arr[high]>=pivot):
            high-=1
        if (low < high):
            arr[low],arr[high]=arr[high],arr[low]

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

def quickSort(arr,low,high):
    if(low <high):
        p=partion(arr,low,high)
        quickSort(arr,low,p-1)
        quickSort(arr,p+1,high)

正确的快速排序代码 #

def swap(a, b, arr):
    if a!=b:
        tmp = arr[a]
        arr[a] = arr[b]
        arr[b] = tmp

def partion(arr,low,high):
    partion_index=low
    pivot=arr[partion_index]

    while (low < high):
        while low < len(arr) and (arr[low]<=pivot):
            low+=1
        while (arr[high]>=pivot):
            high-=1
        if (low < high):
            swap(low, high, arr)
        
    swap(partion_index, high, arr)
    return high

原因分析 #

核心错误出在基准值归位的步骤：

• 错误代码中，pivot = arr[partion_index]是将数组对应位置的值复制到了pivot变量中，这个变量和数组本身没有关联。最后一步的pivot, arr[high] = arr[high], pivot只是交换了pivot变量的取值和arr[high]的取值，完全没有修改数组中原基准值所在的partion_index位置的元素，导致基准值没有被放到正确的分割位置，整个排序的分区逻辑彻底失效。
• 正确代码中，swap(partion_index, high, arr)直接操作数组，将原基准值所在的partion_index位置元素和high位置元素交换，这才真正完成了基准值的归位，符合快速排序分区后基准值处于中间正确位置的要求。

另外需要说明：两段代码中中间交换low和high位置元素的逻辑是等价的——错误代码里的arr[low],arr[high]=arr[high],arr[low]和正确代码里的swap(low, high, arr)作用完全一致，问题只出在最后基准值的处理步骤上。

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