混合快速排序C#实现优化问询：大测试用例超时问题

问题背景 #

现有C#实现的混合排序算法（子数组大小≤阈值时停止快速排序，最终全局执行插入排序）在处理大测试用例时出现超时，以下是针对性的优化方案：

核心优化点 #

1. 优化基准点选择（解决有序数组退化问题） #

原代码固定选取子数组第一个元素作为基准，在数组接近有序时会导致快速排序时间复杂度退化为O(n²)。改用三数取中法选择基准，能有效平衡分区：

static public int Partition(float[] numbers, int low, int high)
{
    // 三数取中：取low、mid、high的中间值作为基准
    int mid = low + (high - low) / 2;
    if (numbers[mid] < numbers[low])
    {
        float temp = numbers[low];
        numbers[low] = numbers[mid];
        numbers[mid] = temp;
    }
    if (numbers[high] < numbers[low])
    {
        float temp = numbers[low];
        numbers[low] = numbers[high];
        numbers[high] = temp;
    }
    if (numbers[high] < numbers[mid])
    {
        float temp = numbers[mid];
        numbers[mid] = numbers[high];
        numbers[high] = temp;
    }
    // 将基准移到low位置，复用原有分区逻辑
    float tempPivot = numbers[low];
    numbers[low] = numbers[mid];
    numbers[mid] = tempPivot;
    float pivot = numbers[low];
    
    int i = low;
    int j = high;
    while (i < j)
    {
        do
        {
            i++;
        } while (i <= high && numbers[i] <= pivot); // 修正边界，避免遗漏high位置元素
        do
        {
            j--;
        } while (j >= low && numbers[j] > pivot);
        if (i < j)
        {
            float temp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = temp;
        }
    }
    float tempSwap = numbers[low];
    numbers[low] = numbers[j];
    numbers[j] = tempSwap;
    return j;
}

2. 调整插入排序时机（减少全局排序工作量） #

原代码最后对整个数组执行插入排序，实际上快排终止后每个小分区已基本有序，直接对小分区执行插入排序，比全局插排效率更高：

static public void QuickSort(float[] numbers, int low, int high, int threshold)
{
    while (high - low + 1 > threshold) // 用循环替代递归，减少栈开销
    {
        int partitionIdx = Partition(numbers, low, high);
        // 优先处理更小的分区，降低递归深度
        if (partitionIdx - low < high - partitionIdx)
        {
            QuickSort(numbers, low, partitionIdx, threshold);
            low = partitionIdx + 1;
        }
        else
        {
            QuickSort(numbers, partitionIdx + 1, high, threshold);
            high = partitionIdx;
        }
    }
    // 直接对当前小分区执行插入排序，而非等待全局处理
    InsertionSort(numbers, low, high);
}

// 修改插入排序，支持指定区间
static public void InsertionSort(float[] numbers, int start, int end)
{
    for (int i = start + 1; i <= end; i++)
    {
        float val = numbers[i];
        int j = i - 1;
        while (j >= start && numbers[j] > val)
        {
            numbers[j + 1] = numbers[j];
            j--;
        }
        numbers[j + 1] = val;
    }
}

// 主函数简化，不再需要全局插排
static public float[] RequiredFunction(float[] numbers, int N, int threshold)
{
    QuickSort(numbers, 0, N - 1, threshold);
    return numbers;
}

3. 消除Swap函数调用开销 #

原Swap函数的ref调用存在额外开销，直接在代码中内联交换逻辑（已在上述代码中替换）。

4. 优化递归深度（小分区优先处理） #

通过优先处理更小的分区，减少递归栈的深度，避免栈溢出风险，同时降低递归调用的开销（已在QuickSort函数中实现）。

额外建议 #

• 阈值选择：建议将阈值设置在10~20之间（可根据测试调整），过小会导致递归次数过多，过大则无法发挥插入排序在小有序数组上的优势。
• 避免重复计算：在QuickSort中，high - low + 1可提前计算一次，减少重复运算。

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