快速排序以第二个元素（arr[1]）为基准的分区问题求助

你的分区代码逻辑存在多处错误，导致无法完成以arr[1]为基准的正确分区：

1. j的更新逻辑错误：你用if arr[i] >= pivot: j = i会让j被所有大于等于基准的元素索引覆盖，无法正确标记小于基准的区域位置。
2. 交换条件限制过严：i > 1的条件导致前两个元素（包括基准本身）没有被纳入分区处理，基准始终停留在原位置。
3. 未将基准移到分界位置：分区完成后，基准应该处于"小于它的元素"和"大于等于它的元素"之间，你的代码没有完成这一步。

1. 正确的分区函数（原地修改，以子数组第二个元素为基准） #

def partition(arr, low, high):
    # 选择当前子数组的第二个元素作为基准（对应原问题的arr[1]，子数组范围是low到high）
    pivot_idx = low + 1
    pivot = arr[pivot_idx]
    # 将基准移到子数组末尾，避免遍历过程中干扰判断
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    
    # j 标记小于基准的区域的下一个插入位置
    j = low
    for i in range(low, high):
        if arr[i] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            j += 1
    
    # 将基准移到正确的分界位置
    arr[j], arr[high] = arr[high], arr[j]
    return j  # 返回基准的最终索引，用于递归拆分

2. 完整的原地快速排序函数 #

def quicksort(arr):
    def helper(low, high):
        if low < high:
            # 获取基准的位置，拆分数组
            pivot_pos = partition(arr, low, high)
            # 递归排序基准左侧的子数组
            helper(low, pivot_pos - 1)
            # 递归排序基准右侧的子数组
            helper(pivot_pos + 1, high)
    
    helper(0, len(arr) - 1)
    return arr

测试验证 #

# 测试分区函数
arr = [34, 8, 3, 4, 5, 67, 43]
partition(arr, 0, len(arr)-1)
print(arr)  # 输出: [3, 4, 5, 8, 67, 34, 43]（基准8处于正确分界位置）

# 测试完整排序
arr = [34, 8, 3, 4, 5, 67, 43]
quicksort(arr)
print(arr)  # 输出: [3, 4, 5, 8, 34, 43, 67]

关键逻辑说明 #

• 先将基准移到子数组末尾，是为了避免在遍历过程中基准元素被误交换，简化分区逻辑。
• 变量j始终跟踪小于基准的区域的下一个空位，遇到符合条件的元素就交换到该位置，确保j左侧全是小于基准的元素。
• 最后将基准移到j的位置，此时数组被拆分为三部分：[low..j-1]（小于基准）、arr[j]（基准）、[j+1..high]（大于等于基准），满足快速排序的分区要求。

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