桶排序-分割错误

Question

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

我的程序做

我的程序读取一个整数文件和文件中的整数数，并输出文件中至少超过文件中数字的90%的最低数字。

我用快速排序法成功地让这件事生效了。然而，我没有得到正确的输出桶排序，我也不知道为什么，因为我的代码似乎是正确的。

在运行时，我会得到一个分段错误。

我的桶排序代码&输出结果

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]])++; 

你写得太出格了。

试试这个：

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);
}