原地排序版Python快速排序问题：子数组正常却无法合并为最终有序数组

嘿，我一眼就瞅出你代码里的关键问题啦：你用了Python的切片操作ar[:wall]和ar[wall+1:]，但切片会创建原列表的副本，不是直接操作原数组的子部分！这就导致你递归排序的都是新生成的小列表，原数组ar的对应段根本没被改动，最后自然没法合并成有序数组咯。

核心修复思路 #

要实现真正的原地快速排序，我们不需要传递切片副本，而是传递原数组+子数组的索引范围，这样所有操作都直接在原数组上进行，递归修改的也是原数组的对应部分。

修复后的完整代码 #

def quickSort(ar, low=0, high=None):
    # 第一次调用时自动初始化high为数组最后一个元素的索引
    if high is None:
        high = len(ar) - 1
    
    # 只有当子数组长度大于1时才需要排序
    if low < high:
        pivot = ar[high]
        wall = low
        # 遍历当前子数组中除pivot外的所有元素
        for i in range(low, high):
            if ar[i] <= pivot:
                ar[wall], ar[i] = ar[i], ar[wall]
                wall += 1
        # 将pivot交换到正确的位置（wall所在处）
        ar[wall], ar[high] = ar[high], ar[wall]
        # 递归排序pivot左侧和右侧的子数组
        quickSort(ar, low, wall - 1)
        quickSort(ar, wall + 1, high)

关键修改点说明 #

• 新增low和high参数：用来标记当前要排序的子数组在原数组中的起始和结束索引，默认值让你可以直接用quickSort(数组)调用，不用手动传索引
• 修正遍历范围：原来的range(len(ar)-2)会忽略倒数第二个元素，现在改成range(low, high)，能精准覆盖当前子数组的所有元素（除了作为pivot的最后一个元素）
• 递归传递索引：不再用切片生成副本，而是直接传递原数组+对应的索引范围，确保所有修改都作用在原数组上

测试示例 #

你可以这样测试修复后的代码：

test_arr = [3, 1, 4, 1, 5, 9, 2, 6]
quickSort(test_arr)
print(test_arr)  # 输出: [1, 1, 2, 3, 4, 5, 6, 9]

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