You need to enable JavaScript to run this app. 如何在Python递归实现的快速排序中添加交换与比较计数器
优惠活动
大模型
产品
解决方案
定价
更多

如何在Python递归实现的快速排序中添加交换与比较计数器

递归场景下快速排序的计数实现方法

递归场景的计数和普通函数的核心差异是:函数调用是嵌套逐层深入、再逐层返回的,计数值不能只向下传递不向上回收,否则深层递归的计数根本无法累计到最外层。这里有两种可直接套用的实现方案,完全适配你现有代码的结构:

方案1:值透传模式(和你已掌握的普通函数传数逻辑完全一致)

你已经会在普通函数间通过「传参+返回值」传递计数,只需要把递归路径上的透传链路补全即可,不需要额外学习新语法:

  • 改造Partition函数:在函数内部累计本轮分区的比较次数、交换次数,除了返回pivot的最终位置,同时把累计的两个计数值一起返回
  • 改造QuickSort函数:
    • 接住Partition返回的计数值,把当前累计的总计数作为参数传给左右两个子递归调用
    • 接住子递归调用返回的最新总计数,继续向上层传递
    • 递归触发终止条件(low >= high)时,把当前累计的计数值原样返回给上一层

常见踩坑:如果调用子递归时只写QuickSort(xxx),既不传当前累计的计数,也不接收子递归返回的计数值,深层递归的计数会完全断流,根本累计不上来。

改造后的代码:

def Partition(array, low, high, compares=0, changes=0):
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
        # 每次执行比较判断,计1次比较
        compares += 1
        if array[j] <= pivot:
            i += 1
            # 发生元素交换,计1次交换
            changes += 1
            array[i], array[j] = array[j], array[i]
    # 最后将pivot归位,也是1次交换
    changes += 1
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1, compares, changes

def QuickSort(array, low, high, compares=0, changes=0):
    if low < high:
        # 接住分区阶段的累计计数
        pivot, p_compares, p_changes = Partition(array, low, high, compares, changes)
        # 将当前累计计数传入左递归,接住左递归的总计数
        total_compares, total_changes = QuickSort(array, low, pivot - 1, p_compares, p_changes)
        # 将左递归累计的总计数传入右递归,接住全流程的最终计数
        total_compares, total_changes = QuickSort(array, pivot + 1, high, total_compares, total_changes)
        return total_compares, total_changes
    # 递归终止时,把当前累计计数返回给上一层
    return compares, changes

# 调用示例
array = [3,1,4,1,5,9,2,6]
final_compares, final_changes = QuickSort(array, 0, len(array)-1)
print(f"排序结果:{array},总比较次数:{final_compares},总交换次数:{final_changes}")

方案2:可变容器共享计数(代码更简洁,适合深层递归)

利用Python中可变对象传引用的特性,用字典、列表这类可变对象作为所有递归层共享的计数器,不需要靠返回值层层透传,所有递归层修改的都是同一个容器内的数值,从根源上避免计数断流:
改造后的代码:

def Partition(array, low, high, counter):
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
        counter["compares"] += 1
        if array[j] <= pivot:
            i += 1
            counter["changes"] += 1
            array[i], array[j] = array[j], array[i]
    counter["changes"] += 1
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1

def QuickSort(array, low, high, counter):
    if low < high:
        pivot = Partition(array, low, high, counter)
        QuickSort(array, low, pivot - 1, counter)
        QuickSort(array, pivot + 1, high, counter)
    return array

# 调用示例
array = [3,1,4,1,5,9,2,6]
counter = {"compares": 0, "changes": 0}
sorted_array = QuickSort(array, 0, len(array)-1, counter)
print(f"排序结果:{sorted_array},总比较次数:{counter['compares']},总交换次数:{counter['changes']}")

计数逻辑校准说明

计数的统计口径要保持一致,避免漏算、错算:

  • 比较次数:每执行一次和pivot的大小判断就计1次,和判断最终为真还是为假无关
  • 交换次数:每发生一次实际的数组元素位置互换就计1次,不要漏掉Partition最后将pivot放到正确位置的那次交换

内容的提问来源于stack exchange,提问作者Jakub Hampl

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.18 11:15:04