c - 桶排序 - 段错误

Question

所以我在程序中使用了快速排序，但现在想将复杂度降低到 O(n)。我需要使用桶排序才能工作。

我的程序做的

我的程序读入一个整数文件，以及文件中整数的个数，并输出文件中至少超过文件中整数 90% 的最小数字。

我确实设法让这个工作，使用快速排序。 但是，我没有通过桶排序得到正确的输出，我也不知道为什么，因为我的代码似乎是正确的。

运行时出现段错误

我的 Bucket 排序和输出结果的代码

void Bucket_Sort(int array[], int n)
{   
 int i, j;   
 int count[n];  
 for(i=0; i < n; i++)
 {   
  count[i] = 0;   
 }     
 for(i=0; i < n; i++)
 {    
  (count[array[i]])++; 
 }     
 for(i=0,j=0; i < n; i++)
 {   
  for(; count[i]>0;(count[i])--) 
  {       
   array[j++] = i; 
  }  
 }   
}    Bucket_Sort(array, numberOfNumbers);   

     //Output the lowest number in the file which exceeds at least 90% of the numbers in the file.
     for (count = floor(0.9 * numberOfNumbers); count < numberOfNumbers; count ++)
     {
      if (array[count] != array[count + 1])
     {
      output = array[count];
      break;    
     }  
     }  
      printf("The outputs is : "); 
      printf("%d \n", output);

我的程序输出编译，但在运行时出现段错误。

关于我在 BucketSort 中做错了什么有什么想法吗？

谢谢，

丹妮尔

Answer 1

如果n 是<20 并且array 包含最大703K 的数字，这两行加起来就是个问题

int count[n];  
(count[array[i]])++; 

你正在写 waaaay 越界。

试试这个:

void Bucket_Sort(int array[], int n)
{
    int i, j;
    int *count = NULL;

    // find largest
    int mymax = array[0]+1;
    for (i=1; i<n; ++i)
    {
        if (mymax < (array[i]+1))
            mymax = array[i]+1;
    }

    // allocate and zero-fill a proper-sized array
    count = calloc(mymax, sizeof(*count));

    for(i=0; i < n; i++)
        (count[array[i]])++;

    for(i=0,j=0; i < mymax; i++)
    {
        for(; count[i]>0;(count[i])--)
            array[j++] = i;
    }
    free(count);
}