快速排序：元素比较次数统计与基准元素选择方法问询

嘿，针对你在实现快速排序时遇到的两个问题，我结合你的代码给你详细解答：

要统计元素比较次数，核心思路是在每次发生元素比较的地方累加计数器。由于快速排序是递归实现的，我们需要一个能在递归函数间共享的计数器——用Python的可变对象（比如列表）是个不错的选择，避免使用全局变量带来的副作用。

修改后的代码（带比较计数） #

import random

def partition(arr, low, high, count):
    i = low - 1  # 较小元素的索引
    pivot = arr[high]  # 基准元素
    for j in range(low, high):
        # 每次元素比较都计数
        count[0] += 1
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

def quickSort(arr, low, high, count):
    if low < high:
        pi = partition(arr, low, high, count)
        # 递归排序左右子数组
        quickSort(arr, low, pi - 1, count)
        quickSort(arr, pi + 1, high, count)

# 测试代码
arr = random.sample(range(0, 9999), 1000)
n = len(arr)
comparison_count = [0]  # 用列表存储计数，实现跨函数修改
quickSort(arr, 0, n-1, comparison_count)

print("Sorted array is:")
for i in range(n):
    print("%d" % arr[i])
print(f"Total element comparisons: {comparison_count[0]}")

关键说明 #

• 我们用count[0]来存储计数，因为列表是可变对象，函数内部修改会影响外部的列表值。
• 所有元素比较都发生在partition函数的for循环中（判断arr[j] <= pivot），每次判断都累加计数。

基准元素的选择直接影响快速排序的效率，常见的选择策略有以下几种，我重点说你需要的「第一个元素作为基准」的实现：

策略1：选择第一个元素作为基准 #

如果要把第一个元素作为基准，需要调整partition函数的逻辑（原代码选的是最后一个元素）。这里推荐用双指针法来重新实现分区：

import random

def partition(arr, low, high, count):
    pivot = arr[low]  # 选择第一个元素作为基准
    left = low + 1
    right = high
    done = False

    while not done:
        # 从左向右找大于基准的元素
        while left <= right and arr[left] <= pivot:
            count[0] += 1
            left += 1
        count[0] += 1  # 退出循环时的最后一次比较也要计数
        
        # 从右向左找小于等于基准的元素
        while arr[right] >= pivot and right >= left:
            count[0] += 1
            right -= 1
        count[0] += 1  # 退出循环时的最后一次比较
        
        if right < left:
            done = True
        else:
            # 交换左右指针指向的元素
            arr[left], arr[right] = arr[right], arr[left]
    
    # 将基准元素放到正确的位置（right指针的位置）
    arr[low], arr[right] = arr[right], arr[low]
    return right

def quickSort(arr, low, high, count):
    if low < high:
        pi = partition(arr, low, high, count)
        quickSort(arr, low, pi - 1, count)
        quickSort(arr, pi + 1, high, count)

# 测试代码
arr = random.sample(range(0, 9999), 1000)
n = len(arr)
comparison_count = [0]
quickSort(arr, 0, n-1, comparison_count)

print("Sorted array is:")
for i in range(n):
    print("%d" % arr[i])
print(f"Total element comparisons: {comparison_count[0]}")

其他常见基准选择策略 #

• 随机选择基准：从待排序区间随机选一个元素作为基准，避免数组已排序时出现最坏时间复杂度（O(n²)）。只需在partition开头加一行随机交换代码即可：

  pivot_idx = random.randint(low, high)
  arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
  pivot = arr[high]
  

• 三数取中：选择区间第一个、中间、最后一个元素的中位数作为基准，进一步优化性能，减少最坏情况的概率。

内容的提问来源于stack exchange，提问作者Maxim Potapov