特定大小数组下Quicksort排序失效问题求助

我需要测试快速排序在10000、20000……100000个整数的升序、降序、随机数组上的执行时间。随机数组在所有规模下都能正常运行，但升序和降序数组超过某个阈值后就会失效：我这边测试30590个元素可行，30591就不行；朋友也遇到类似问题，阈值在30000-40000之间。数组从文件读取，我确认读取代码没问题（自己创建数组也会出现同样问题），而且这些文件用于冒泡排序和归并排序时完全正常。

我的代码 #

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

void get_array(FILE *fp, int len, int vector[]);
void write_array(FILE *fp, int vector[],int len);
void quicksort(int v[], int i, int d);
int pivote(int primero, int ultimo, int v[]);

int main(void)
{
    FILE *fp;
    int *pv, len, i, j;
    clock_t start;
    
    for (i=1;i<11;i++)
    {   
        len = i*10000;
        //len = 30590; //this works, 30591 doesn't
        int vector[len];
        clock_t start;
        
        //random
        fp = fopen("aleatorio.txt","r");
        get_array(fp,len,vector);
        start = clock();
        quicksort(0, len-1,vector);
        printf("\nRandom n=%d secs: %f\n", len, (float)(clock() - start)/CLOCKS_PER_SEC);
        fclose(fp);
        fp = fopen("aleatorio_output.txt","w");
        write_array(fp, vector, len);
        fclose(fp);
        
        //descendente
        fp = fopen("descendente.txt","r");
        get_array(fp,len,vector);
        start = clock();
        quicksort(vector,0,len-1);  
        printf("Descendente n=%d secs: %f\n", len, (float)(clock() - start)/CLOCKS_PER_SEC);
        fclose(fp);
        fp = fopen("descendente_output.txt","w");
        write_array(fp, vector, len);
        fclose(fp);
        
        //ascendente
        fp = fopen("ascendente.txt","r");
        get_array(fp,len,vector);
        fclose(fp);
        start = clock();
        printf("Ascendente n=%d secs: %f\n", len, (float)(clock() - start)/CLOCKS_PER_SEC);
        fp = fopen("ascendente_output.txt","w");
        write_array(fp, vector,  len);
        fclose(fp);
    }
}

void quicksort(int v[], int izquierda, int derecha)
{
    int p;
    if (derecha>izquierda)
    {
        p = pivote(izquierda,derecha,v);
        quicksort(v,izquierda, p-1);
        quicksort(v,p+1, derecha);
    }
}

int pivote (int primero, int ultimo, int v[])
{
    int pivote = v[primero], i = primero, j = ultimo+1, aux;
    while (i<j) //hasta que se crucen los indices
    {
        do{
        i++;}while (v[i]<pivote && i<ultimo); 

        do{
        j--;}while (v[j]>pivote);
            
        if(i<j)
        {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
        }
    }
    v[primero] = v[j];
    v[j] = pivote;
    return j;
}

//devuelve un vector de enteros extraido de un fichero
void get_array(FILE *fp,int len, int vector[]) 
{
    int i=0;
    while (!feof(fp) && i<len)
    {
        fscanf(fp,"%d",&vector[i]);
        i++;
    }
}

//escribe los numeros de un vector de enteros en un fichero
void write_array(FILE *fp, int vector[],int len)
{
    int i;
    for (i=0; i<len; i++)
        fprintf(fp,"%d\n",vector[i]);
}

核心问题 #

1. 栈溢出（触发失效的直接原因）
   你的快速排序选择第一个元素作为基准，在处理升序/降序数组时，递归深度会达到O(n)级别。而程序栈的空间有限（通常默认几MB），当数组规模超过阈值时，递归调用会耗尽栈空间，导致程序崩溃。随机数组的递归深度平均为O(logn)，因此不会触发栈溢出。

2. 函数调用参数顺序错误
   随机数组排序时，你调用quicksort(0, len-1,vector);，但quicksort函数定义的参数顺序是void quicksort(int v[], int izquierda, int derecha)，参数顺序完全颠倒，会导致未定义行为。

3. 升序数组排序逻辑缺失
   升序数组的处理代码中，读取数组后没有调用quicksort就直接输出时间，属于明显的逻辑错误。

修复步骤 #

1. 优化基准选择，降低递归深度
   使用三数取中法选择基准，避免有序数组下的最坏递归深度：

   int pivote(int primero, int ultimo, int v[])
   {
       // 三数取中：取首、尾、中间元素的中位数作为基准
       int mid = primero + (ultimo - primero)/2;
       // 交换首元素和中位数，保证基准是中位数
       if(v[primero] > v[mid]) {
           int aux = v[primero];
           v[primero] = v[mid];
           v[mid] = aux;
       }
       if(v[primero] > v[ultimo]) {
           int aux = v[primero];
           v[primero] = v[ultimo];
           v[ultimo] = aux;
       }
       if(v[mid] > v[ultimo]) {
           int aux = v[mid];
           v[mid] = v[ultimo];
           v[ultimo] = aux;
       }
       // 将中位数交换到首位置作为基准
       int aux = v[primero];
       v[primero] = v[mid];
       v[mid] = aux;
   
       int pivote_val = v[primero], i = primero, j = ultimo+1;
       while (i < j)
       {
           do{
               i++;
           }while (v[i] < pivote_val && i < ultimo); 
   
           do{
               j--;
           }while (v[j] > pivote_val);
               
           if(i < j)
           {
               aux = v[i];
               v[i] = v[j];
               v[j] = aux;
           }
       }
       v[primero] = v[j];
       v[j] = pivote_val;
       return j;
   }
   

2. 修正函数调用参数顺序
   将随机数组的排序调用改为：

   quicksort(vector, 0, len-1);
   

3. 补全升序数组的排序步骤
   在升序数组读取后添加排序调用：

   //ascendente
   fp = fopen("ascendente.txt","r");
   get_array(fp,len,vector);
   fclose(fp);
   start = clock();
   quicksort(vector, 0, len-1); // 补全排序调用
   printf("Ascendente n=%d secs: %f\n", len, (float)(clock() - start)/CLOCKS_PER_SEC);
   fp = fopen("ascendente_output.txt","w");
   write_array(fp, vector,  len);
   fclose(fp);
   

4. 改用堆分配数组（可选）
   当前使用的变长数组int vector[len];分配在栈上，大数组会占用大量栈空间。可以改用堆分配：

   int *vector = malloc(len * sizeof(int));
   if(vector == NULL) {
       perror("malloc failed");
       exit(EXIT_FAILURE);
   }
   // 使用完成后释放内存
   free(vector);
   

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