Python排序算法时间复杂度与计时测量异常排查

从你提供的代码和输出来看，计时结果存在明显异常，核心问题和优化方向如下：

1. 快排计时显示为0的原因 #

你的快排实现速度确实远快于冒泡/选择排序，但显示0.000000并非真的耗时为0，而是计时器精度限制导致的：

• time.process_time()在Windows系统下的精度通常为15.625ms（1/64秒），如果快排运行时间低于这个阈值，就会被统计为0。
• time.time()的精度受系统时钟影响，对于微秒级的短任务测量准确性不足。

2. 壁钟时间远大于CPU时间的异常原因 #

壁钟时间包含进程等待CPU、系统调度等所有耗时，而CPU时间仅统计进程实际占用CPU的时间。两者差距过大，可能是以下原因：

• 你的实际冒泡/选择排序实现中存在不必要的阻塞逻辑（比如意外的IO、sleep调用），或者测试时系统资源紧张，进程被频繁调度。
• 单次测量受系统波动影响极大，比如后台有高负载进程抢占资源。

3. 测量函数的优化方案 #

改用高精度计时器+多次取平均 #

替换低精度计时器，并通过多次运行取平均减少系统波动的影响：

import random
import time

def generate_random_array(size):
    return [random.randint(1, 1000) for _ in range(size)]

# 此处替换为你实际的冒泡/选择排序实现
def bubble_sort(array):
    n = len(array)
    count = 0
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            count +=1
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
                swapped = True
                count +=1
        if not swapped:
            break
    return count

def selection_sort(array):
    n = len(array)
    count = 0
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            count +=1
            if array[min_idx] > array[j]:
                min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i]
        count +=1
    return count

def quick_sort(array):
    comparisons = [0]  
    swaps = [0]
    operations_counter = [0]  

    def partition(array):
        if len(array) <= 1:
            return array
        else:
            pivot = array[0]
            less = []
            equal = []
            greater = []
            for x in array:
                comparisons[0] += 1
                operations_counter[0] += 1  
                if x < pivot:
                    less.append(x)
                    operations_counter[0] += 1  
                elif x == pivot:
                    equal.append(x)
                    operations_counter[0] += 1  
                else:
                    greater.append(x)
                    operations_counter[0] += 1  
            operations_counter[0] += 1  
            return partition(less) + equal + partition(greater)

    partition(array)
    return comparisons[0] + swaps[0] + operations_counter[0]

def measure_sorting_time_and_complexity(sort_func, array, runs=5):
    total_wall = 0.0
    total_cpu = 0.0
    total_complexity = 0

    for _ in range(runs):
        arr_copy = array.copy()
        wall_start = time.perf_counter()
        cpu_start = time.process_time()

        complexity = sort_func(arr_copy)

        wall_end = time.perf_counter()
        cpu_end = time.process_time()

        total_wall += wall_end - wall_start
        total_cpu += cpu_end - cpu_start
        total_complexity += complexity

    avg_wall = total_wall / runs
    avg_cpu = (total_cpu / runs) * 1000  # 转换为毫秒
    avg_complexity = total_complexity // runs

    return avg_complexity, avg_wall, avg_cpu

array_sizes = [1000]

for size in array_sizes:
    print(f"Creating an array of size {size}")
    array = generate_random_array(size)

    # Measure and print Bubble Sort performance
    print("*** Bubble Sort ***")
    bubble_complexity, bubble_wall_time, bubble_cpu_time = measure_sorting_time_and_complexity(bubble_sort, array)
    print(f"Execution time: {bubble_cpu_time:.6f} milliseconds")
    print(f"Wallclock time: {bubble_wall_time:.6f} seconds")
    print(f"Complexity: {bubble_complexity}")

    # Measure and print Selection Sort performance
    print("*** Selection Sort ***")
    selection_complexity, selection_wall_time, selection_cpu_time = measure_sorting_time_and_complexity(selection_sort, array)
    print(f"Execution time: {selection_cpu_time:.6f} milliseconds")
    print(f"Wallclock time: {selection_wall_time:.6f} seconds")
    print(f"Complexity: {selection_complexity}")

    # Measure and print Quick Sort performance
    print("*** Quicksort (Recursive) ***")
    quick_complexity, quick_wall_time, quick_cpu_time = measure_sorting_time_and_complexity(quick_sort, array)
    print(f"Execution time: {quick_cpu_time:.6f} milliseconds")
    print(f"Wallclock time: {quick_wall_time:.6f} seconds")
    print(f"Complexity: {quick_complexity}")

其他注意事项 #

• 确认你的bubble_sort和selection_sort实现没有隐藏的低效逻辑（比如冒泡排序未加入提前终止条件），低效逻辑会放大系统波动的影响。
• 测试时尽量关闭后台高负载进程，减少系统调度对计时的干扰。

修改后，快排会显示出真实的微小耗时，冒泡/选择的壁钟时间与CPU时间差距会缩小，结果更符合预期。

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