基于Slice对象的Python快速排序函数输出异常，分区函数正常

我懂这种挫败感——分区函数的doctest明明跑通了，结果递归调用quicksort_slice就完全不对，调试半天发现是交换逻辑和参数更新的问题对吧？别慌，咱们一步步把它修好。

问题根源复盘 #

你已经定位到核心问题：要么是递归时传递的分区边界没对应上基准元素的最终位置，要么是基准值（piv）的参数没更新，再就是循环里的交换步骤漏了关键环节。结合Slice对象的结构（{'data': numpy数组, 'left': 左索引, 'right': 右索引}），咱们直接针对这几点修复。

具体修复步骤 #

这里我给你整理了关键的修复点，附带上完整的代码示例：

1. 必须更新基准值的位置
   分区完成后，基准元素已经被放到了它最终排序后的位置，递归调用时必须用这个新的piv索引来划分左右子数组，绝对不能用原来的基准初始位置。

2. 调整递归的循环范围
   基准元素已经有序，所以递归只需要处理left到piv-1（左子数组）和piv+1到right（右子数组）的范围，别把基准元素再包含进去重复处理。

3. 补全基准归位的交换步骤
   分区函数的最后一步一定要把基准元素交换到正确的位置，这是快速排序分区的核心，漏了这步直接会导致整个排序逻辑混乱。

修复后的完整代码 #

import numpy as np

def partition(slice_obj):
    data = slice_obj['data']
    left = slice_obj['left']
    right = slice_obj['right']
    
    # 选最右侧元素作为基准
    pivot_val = data[right]
    # 初始化小于基准的元素的边界指针
    i = left - 1
    
    # 遍历当前区间内的元素
    for j in range(left, right):
        if data[j] <= pivot_val:
            i += 1
            # 交换当前元素到小于基准的区域
            data[i], data[j] = data[j], data[i]
    
    # 最后把基准元素交换到正确的位置
    data[i + 1], data[right] = data[right], data[i + 1]
    # 返回基准元素的最终索引
    return i + 1

def quicksort_slice(slice_obj):
    left = slice_obj['left']
    right = slice_obj['right']
    
    # 只有当区间内有至少两个元素时才递归
    if left < right:
        # 先分区，拿到基准元素的最终位置
        piv = partition(slice_obj)
        
        # 递归排序左子数组（不包含基准）
        quicksort_slice({
            'data': slice_obj['data'],
            'left': left,
            'right': piv - 1
        })
        
        # 递归排序右子数组（不包含基准）
        quicksort_slice({
            'data': slice_obj['data'],
            'left': piv + 1,
            'right': right
        })

测试验证 #

你可以用这个测试用例验证修复后的效果：

test_slice = {
    'data': np.array([3, 1, 4, 1, 5, 9, 2, 6]),
    'left': 0,
    'right': 7
}

quicksort_slice(test_slice)
print(test_slice['data'])  # 输出应为：[1 1 2 3 4 5 6 9]

关键提醒 #

如果你的原代码里，递归时没有用partition返回的piv值，而是硬编码了某个索引，或者递归范围包含了基准元素，那肯定会出现排序错误。另外，确保partition里的交换逻辑没有遗漏，尤其是最后把基准元素移到中间的那一步——这是很多新手容易漏掉的点。

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