Python快速排序实现疑问：长度为2数组的基础场景原理困惑

一、长度为2的数组处理逻辑 #

以数组[5,4]为例，完整执行流程如下：

1. 调用quicksort([5,4], 0, 1)，满足low < high，进入partition函数。
2. 选择最后一个元素4作为pivot，初始化left_wall=0，right_wall=high-1=0。
3. 外层while left_wall < right_wall（0 < 0）不成立，直接跳过循环。
4. 交换pivot（索引1的元素）和right_wall（索引0的元素），数组变为[4,5]，返回right_wall=0。
5. 递归调用quicksort(arr, 0, -1)（不满足low < high，直接返回）和quicksort(arr, 1, 1)（同样直接返回），排序完成。

核心逻辑：即使左右指针直接相遇，最后pivot与相遇点的交换操作会完成剩余排序——相遇点的位置就是pivot应处的正确位置。

二、你的代码存在的问题 #

1. 内层循环无边界限制，导致索引越界
   比如处理[3,4]时，第一个内层while arr[left_wall] <= pivot：arr[0]=3 <=4，left_wall会加1到1，此时arr[1]是pivot，循环仍会执行left_wall +=1，变成2，超出数组索引范围（数组长度为2，最大索引是1），直接报错。
2. 右指针循环未处理边界
   当所有元素都大于等于pivot时，right_wall会不断减1，可能小于low，导致索引错误。

三、修正后的代码 #

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)
    return arr

def partition(arr, low, high):
    # 选择最后一个元素作为pivot
    pivot = arr[high]
    left_wall = low
    right_wall = high - 1

    while left_wall <= right_wall:
        # 左指针找大于pivot的元素，同时不超过右指针边界
        while left_wall <= right_wall and arr[left_wall] <= pivot:
            left_wall += 1
        # 右指针找小于pivot的元素，同时不低于左指针边界
        while left_wall <= right_wall and arr[right_wall] >= pivot:
            right_wall -= 1
        # 找到可交换的左右元素
        if left_wall < right_wall:
            arr[left_wall], arr[right_wall] = arr[right_wall], arr[left_wall]
    
    # 将pivot放到正确的位置：left_wall此时是第一个大于pivot的位置
    arr[high], arr[left_wall] = arr[left_wall], arr[high]
    return left_wall

# 测试
print(quicksort([5,4,3,2], 0, 3))  # 输出: [2, 3, 4, 5]
print(quicksort([5,4], 0, 1))      # 输出: [4, 5]

四、修正后的关键改动说明 #

• 外层循环改为left_wall <= right_wall，确保指针能覆盖所有需要比较的元素。
• 内层循环增加left_wall <= right_wall的边界判断，彻底避免索引越界。
• 最后交换pivot时，使用left_wall而非right_wall：循环结束后，left_wall一定指向第一个大于pivot的元素位置，这正是pivot应该插入的位置（pivot左边全是<=它的元素，右边全是>=它的元素）。

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