1

所以我在我的程序中使用了快速排序，但现在想将我的复杂度降低到 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 中做错了什么的任何想法？

谢谢，

丹妮尔

4

1 回答 1

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);
}
于 2013-11-14T21:19:01.243 回答