c - C中的慢基数排序

Question

我必须按升序对数组中的数字进行排序，我的时间复杂度必须为 O(n)。我正在使用基数排序，但速度不够快。有什么想法可以让我的代码更快吗？在这里:

void radix(int *a, int n) { 

    int i;
    int sorted[n];
    int number = 1;
    int biggestNumber = -1;

 for(i = 0; i < n; i++){
     if(a[i] > biggestNumber)
        biggestNumber = a[i]; }


while (biggestNumber / number > 0){

 int bucket[10] = { 0 };

    for (i = 0; i < n; i++)
      bucket[(a[i] / number) % 10]++;

    for (i = 1; i < 10; i++)
      bucket[i] += bucket[i - 1];

    for (i = n - 1; i >= 0; i--)
      sorted[--bucket[(a[i] / number) % 10]] = a[i];


   for (i = 0; i < n; i++)
      a[i] = sorted[i];

      number*= 10; } }

Answer 1

评论 - 排序似乎只适用于正数，如果 a[i] 为负数，则负索引用于 bucket[...] 和 sorted[...]。如果不需要有符号整数，您可以将其更改为对无符号整数进行排序。没有检查 number *= 10 的溢出。 sorted 是从堆栈分配的，如果 n 很大，这将不起作用。使用 malloc() 为排序分配空间。

为了使排序更快:

将基数的底数从 10 更改为 256。为避免可能的溢出，检查 0 == (number *= 256) 以跳出循环。

在每次传递时交替基数排序的方向。第一次从 a 到 sorted，下一次从 sorted 到 a。这是最简单的方法，使用一对指针，在每次通过时交换指针，然后在排序完成后，检查排序后的数据是否在 a[] 中结束，如果没有，则从 sorted[] 复制到 a[]。

使桶成为矩阵。假设 int 是 32 位，基数是 256，那么 bucket 就是 [4][256]。这允许单次通过 a[] 来创建桶矩阵。如果 int 是 64 位，则 bucket 将为 [8][256]。