如何在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
相关产品推荐
相关产品推荐

