Python实现取中间元素为基准的原地快速排序比较次数远超预期排查

• 存在与元素比较完全无关的无效计数
  代码中quicksort函数末尾的addComparison()是无条件执行的，它统计的是递归函数的调用次数（包括所有触发基线条件的叶子节点调用），并非数组元素与pivot的实际比较次数。对应当前23个元素的测试用例，递归树总共会产生45次函数调用，这部分就平白累计了45次的无效比较计数，是总差值的主要来源。
• 同一元素被重复计入与pivot的比较
  split_arr的双指针扫描逻辑中，左右两个独立的扫描循环会对重叠位置的元素做双重校验：当扫描到与pivot值相等的元素（包括pivot本身、数组中重复出现的3个10值）时，左扫描循环会因元素不小于pivot停止，右扫描循环又会因元素不大于pivot，对同一个元素再次做一次比较并计数。本次测试用例中这部分累计多算9次，加上前面的45次无效计数，刚好凑成54次的总差值（实际196次 - 预期142次 =54次）。

• 直接移除quicksort函数末尾的addComparison()调用，彻底清除与元素比较无关的冗余计数。
• 优化split_arr的扫描逻辑，消除重复计数：
  • 双指针扫描过程中，一旦左右指针位置发生交叉/重叠，立刻停止越界的扫描动作，不对已经被另一指针扫描过的元素重复执行比较与计数。
  • 可在扫描启动前，将选中的中间位置pivot元素临时交换到子数组的边界位置（如子数组左端点），让扫描范围从紧邻边界的位置开始，避免pivot本身被左右两个扫描循环重复比较。

comparisons = 0

def addComparison() -> bool:
    global comparisons
    comparisons += 1
    return True

def quicksort(arr_list: list, lower_bound: int, upper_bound: int) -> list:
    if upper_bound > lower_bound:
        index = split_arr(arr_list, lower_bound, upper_bound)
        quicksort(arr_list, lower_bound, index)
        quicksort(arr_list, index+1, upper_bound)

def split_arr(arr_list: list, lower_bound: int, upper_bound: int) -> int:
    pivot_index = (lower_bound + upper_bound) // 2
    pivot_elem  = arr_list[pivot_index]
    # 临时将pivot交换到左边界，避免扫描时重复比较pivot本身
    arr_list[lower_bound], arr_list[pivot_index] = arr_list[pivot_index], arr_list[lower_bound]

    scan_left = lower_bound + 1
    scan_right = upper_bound

    while scan_left <= scan_right:
        while scan_left <= scan_right and addComparison() and arr_list[scan_left] < pivot_elem:
            scan_left += 1
        
        while scan_right >= scan_left and addComparison() and arr_list[scan_right] > pivot_elem:
            scan_right -= 1
        
        if scan_left < scan_right:
            arr_list[scan_left], arr_list[scan_right] = arr_list[scan_right], arr_list[scan_left]
            scan_left += 1
            scan_right -= 1
    
    # 交换pivot到最终位置
    arr_list[lower_bound], arr_list[scan_right] = arr_list[scan_right], arr_list[lower_bound]
    return scan_right

内容的提问来源于stack exchange，提问作者418 teapot