快速排序性能瓶颈与优化需求

快速排序作为分治算法的典型代表，其平均时间复杂度为 O(n log n)，但在面对已排序或重复元素密集的数据时，可能退化至 O(n²)。这种性能下降主要源于基准值（pivot）选择不当导致的不平衡划分。

核心问题分析

• 划分不均：若每次选取的基准都是最大或最小值，递归深度将逼近线性。
• 重复元素处理低效：传统分区方式对相等元素仍进行递归，造成冗余计算。
• 小数组递归开销大：当子数组极小时，函数调用成本超过实际排序收益。

三数取中法的核心思想与实现机制

三数取中法通过从数组首、中、尾三个位置选取中位数作为基准，显著提升划分均衡性，降低最坏情况发生的概率。

算法流程

1. 确定三个关键索引：左端点 low、中间点 mid = low + (high - low) / 2、右端点 high。
2. 通过三次比较调整三者顺序，使 arr[low] ≤ arr[mid] ≤ arr[high]。
3. 将中位数 arr[mid] 交换至 arr[low] 位置，作为后续分区的基准。

C语言实现示例

int median_of_three(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;

    // 确保 arr[low] ≤ arr[mid]
    if (arr[mid] < arr[low]) {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
    }

    // 确保 arr[low] ≤ arr[high]
    if (arr[high] < arr[low]) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    // 确保 arr[mid] ≤ arr[high]
    if (arr[high] < arr[mid]) {
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
    }

    // 此时 arr[mid] 是三数中位数，将其移至开头
    int temp = arr[low];
    arr[low] = arr[mid];
    arr[mid] = temp;

    return low; // 基准索引返回为 low
}

与其他策略的对比与适用场景

策略	优点	适用场景
首/尾元素选基准	实现简单，无额外比较	随机数据，非严格性能要求
随机选取基准	避免恶意输入导致退化	通用环境，安全性要求高
三数取中	平衡性能与开销，对部分有序数据友好	工业级排序，含重复键值数据

混合优化策略：结合插入排序

对于长度小于10的子数组，快速排序的递归开销大于其优势。此时切换至插入排序可大幅提升效率。

void hybrid_quick_sort(int arr[], int low, int high) {
    if (high - low + 1 <= 10) {
        insertion_sort(arr, low, high);
    } else {
        int pivot_idx = median_of_three(arr, low, high);
        int partition_idx = partition(arr, low, high, pivot_idx);

        hybrid_quick_sort(arr, low, partition_idx - 1);
        hybrid_quick_sort(arr, partition_idx + 1, high);
    }
}

总结与工程建议

三数取中法是一种低成本、高效益的优化手段，特别适用于处理接近有序或存在大量重复元素的数据集。在实际系统中，应结合小数组切换策略和三路划分机制，构建稳定高效的排序实现。