Python数组原地Partition实现出错，问询修复方法及递归实现方案

现有代码错误排查 #

现有代码存在3个核心逻辑错误，导致分区结果不符合预期：

• 迭代逻辑冗余：for循环本身会自动完成j的累加，循环内部手动修改j的取值会打乱遍历顺序，且else分支的j + 1没有赋值操作，完全不生效
• 基准值漂移：遍历过程中如果交换到pivot索引对应的元素，后续判断用的a[pivot]就不再是初始的基准值，最后一步交换时pivot索引对应的元素也已经不是原始基准值，导致分区完全失效
• 边界处理错误：没有考虑pivot位置的元素在遍历过程中被提前交换的问题，最终基准值的放置位置错误

修复后的分区代码 #

def swap(a, i, j):
    a[i], a[j] = a[j], a[i]

def Part(a, pivot, left=0, right=None):
    if right is None:
        right = len(a) - 1
    # 先保存基准值，同时把基准值换到右边界避免遍历中被交换
    pivot_val = a[pivot]
    swap(a, pivot, right)
    # 左分区指针，指向最后一个小于等于基准值的元素位置
    i = left - 1
    for j in range(left, right):
        if a[j] <= pivot_val:
            i += 1
            swap(a, i, j)
    # 把基准值换回左分区的下一个位置，也就是基准值的最终正确位置
    swap(a, i + 1, right)
    return i + 1

测试验证 #

对测试数组[1, 3, 6, 1, 5, 4]，取索引为1的元素3作为基准，调用Part(a, 1)后得到的分区结果为[1, 1, 3, 6, 5, 4]，符合分区规则：所有小于等于3的元素在左，大于3的在右，基准值3位于正确的索引2的位置。

递归实现完全排序 #

单次分区只能将数组按基准值拆分为两部分，无法直接得到完全有序的结果。你预期的全排序结果可以通过递归调用分区函数实现，也就是快速排序算法：

def quick_sort(a, left=0, right=None):
    if right is None:
        right = len(a) - 1
    if left >= right:
        return
    # 每次取区间左端点作为基准，也可随机选取避免最坏时间复杂度
    pivot_idx = Part(a, left, left, right)
    # 递归排序左半区（小于等于基准值的部分）
    quick_sort(a, left, pivot_idx - 1)
    # 递归排序右半区（大于基准值的部分）
    quick_sort(a, pivot_idx + 1, right)

测试验证 #

调用quick_sort([1, 3, 6, 1, 5, 4])后，输出结果为[1, 1, 3, 4, 5, 6]，与预期完全一致。

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