快速排序（Quicksort）分区问题求助：我的Python代码存在故障

嘿，我看到你在写快速排序的时候遇到了瓶颈，尤其是Partition函数还没写完，而且现有代码里还有个容易踩的坑，我来帮你搞定它！

先说说现有代码里的问题 #

• 递归终止条件错误：你在Quicksort里写的if len(Array) == 1完全不对哦！因为递归的时候我们处理的是子数组（由left_index和right_index界定），不是整个原数组。正确的终止条件应该是当left_index >= right_index时停止递归——这意味着当前子数组要么只有一个元素，要么是空的，根本不需要排序。
• Partition函数未实现：这可是快速排序的核心逻辑，负责把数组分成比基准小和比基准大的两部分，得补上这部分代码才行。

修正后的完整代码 #

def main(): 
    Array = [10, 5, 3, 8, 6, 7, 4, 9, 2, 1, 10] 
    right_index = len(Array) - 1 
    left_index = 0 
    sorted_array = Quicksort(Array, left_index, right_index)
    print(sorted_array)  # 打印排序结果验证

def Quicksort(Array, left_index, right_index): 
    # 正确的递归终止条件：子数组无需排序时返回
    if left_index >= right_index: 
        return Array 
    pivot_index = Partition(Array, left_index, right_index) 
    # 递归排序基准左边的子数组
    Quicksort(Array, left_index, pivot_index - 1) 
    # 递归排序基准右边的子数组
    Quicksort(Array, pivot_index + 1, right_index) 
    return Array

def Partition(Array, left_index, right_index): 
    # 选最右侧元素作为基准（pivot）
    pivot = Array[right_index]
    # i 用来标记"小于pivot的元素区域"的最后一个位置
    i = left_index - 1

    # 遍历从left到right-1的所有元素
    for j in range(left_index, right_index):
        # 如果当前元素小于等于pivot，就把它移到"小于区域"的下一个位置
        if Array[j] <= pivot:
            i += 1
            Array[i], Array[j] = Array[j], Array[i]
    
    # 最后把pivot放到它的正确位置（i+1）
    Array[i + 1], Array[right_index] = Array[right_index], Array[i + 1]
    # 返回pivot的索引，供递归使用
    return i + 1

if __name__ == "__main__":
    main()

代码说明 #

1. 递归终止条件：改成left_index >= right_index后，能正确识别不需要排序的子数组，避免无效递归。
2. Partition函数逻辑：
   • 选择最右侧元素作为基准，这是快速排序里比较经典的选择方式；
   • 用i指针跟踪小于基准的元素应该放置的位置，遍历过程中把符合条件的元素交换到i的右侧；
   • 最后把基准元素放到i+1的位置，这个位置就是基准在排序后数组里的最终位置，左边全是小于等于它的元素，右边全是大于它的元素。

运行这个代码，你会得到排序后的数组：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10]，完全符合预期~

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