混合快速排序与插入排序的代码调试及性能疑问

首先，我们先解决你代码里的逻辑错误和语法问题，再解释为什么这个混合排序实现比随机快排版本更快。

一、代码中的关键错误与修正版本 #

你的代码存在多个语法和逻辑错误，导致编译报错和功能失效，下面是修正后的完整代码，同时标注错误点：

错误点分析 #

1. 子数组长度计算错误：原代码中n = p - r + 1会得到负数（因为r >= p），正确的长度应该是n = r - p + 1。
2. 条件判断逻辑颠倒：原条件if(n >= t && p > r)完全错误，应该是当子数组长度**大于等于阈值t且数组范围有效（p < r）**时，继续递归混合排序；否则调用插入排序。
3. 插入排序范围硬编码：原代码中for(j = 1; j < 6; j++)固定了排序范围，应该根据当前子数组的p到r来遍历，即for(j = p + 1; j <= r; j++)。
4. 递归调用错误：原代码直接调用纯快排quicksort，应该递归调用hybridsort，这样才能在子数组中继续判断是否切换到插入排序。
5. 函数声明与定义不匹配：原声明int hybridsort(int A[], int p, int q, int t);中的参数q和定义中的r不一致，需要统一。
6. 未提前声明函数：quicksort和partition函数需要在调用前声明，否则编译会报错。
7. 返回语句位置错误：原代码的return count;写在了函数体外，语法错误。

修正后的代码 #

#include<stdio.h>
#include<stdlib.h>

// 提前声明需要用到的函数
int hybridsort(int A[], int p, int r, int t);
void quicksort(int A[], int p, int r);
int partition(int A[], int p, int r);

int main() {
    int n = 9, t = 3;
    int A[9] = {1, 8, 6, 3, 2, 7, 4, 9, 10};
    
    printf("Original array: ");
    for(int i = 0; i < n; i++) printf(" %d", A[i]);
    printf("\n");
    
    int res = hybridsort(A, 0, n - 1, t);
    printf("No. of insertion sort calls = %d\n", res);
    
    printf("Sorted array: ");
    for(int i = 0; i < n; i++) printf(" %d", A[i]);
    printf("\n");
    
    return 0;
}

int hybridsort(int A[], int p, int r, int t){
    int count = 0;
    int subarray_len = r - p + 1;
    
    // 当子数组长度 >= 阈值且范围有效时，继续递归混合排序
    if(subarray_len >= t && p < r){
        int q = partition(A, p, r);
        // 递归处理左右子数组，累加插入排序调用次数
        count += hybridsort(A, p, q - 1, t);
        count += hybridsort(A, q + 1, r, t);
    } else {
        // 子数组长度小于阈值，调用插入排序，计数+1
        count += 1;
        int i, j, key;
        for(j = p + 1; j <= r; j++){
            key = A[j];
            i = j - 1;
            while(i >= p && A[i] > key){
                A[i + 1] = A[i];
                i--;
            }
            A[i + 1] = key;
        }
    }
    return count;
}

void quicksort(int A[], int p, int r){
    if(p < r){
        int q = partition(A, p, r);
        quicksort(A, p, q - 1);
        quicksort(A, q + 1, r);
    }
}

int partition(int A[], int p, int r){
    int x = A[r]; // 选择末尾元素作为pivot
    int i = p - 1;
    int tmp;
    
    for(int j = p; j < r; j++){
        if(A[j] <= x){
            i++;
            tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
    tmp = A[i + 1];
    A[i + 1] = A[r];
    A[r] = tmp;
    
    return i + 1;
}

二、为什么这个混合排序比随机快排版本更快？ #

这个混合排序在实践中更快的核心原因是利用了不同排序算法的常数项优势，具体来说：

1. 插入排序在小数据量下的低常数开销
   快排的优势是平均O(n log n)的时间复杂度，但它的递归调用、partition操作都有额外的开销（比如函数调用栈、元素交换的次数）。而插入排序虽然时间复杂度是O(n²)，但在数据量很小的时候（比如阈值t=5~20），它的实际运行速度更快——因为它的常数项极低，不需要递归，只是简单的元素移动和比较，缓存局部性也更好（顺序访问数组，缓存命中率高）。

2. 避免了随机快排的额外开销
   随机快排通过随机选择pivot来避免最坏情况（比如已排序数组导致快排退化为O(n²)），但随机数生成本身会带来额外的性能开销。而这个混合排序方案：

   • 对于大数据量，用普通快排（末尾pivot）已经能保证平均O(n log n)的效率；
   • 对于小数据量，直接切换到插入排序，既避开了快排的递归开销，也不需要随机数生成的额外成本。

3. 减少了递归深度
   当子数组小于阈值时停止递归，直接用插入排序处理，大大减少了递归调用的次数，降低了栈空间的使用和函数调用的开销。

总的来说，这个混合排序是在时间复杂度和实际运行效率之间做了最优权衡，充分发挥了两种排序算法的优势，所以比纯随机快排的版本运行更快。

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