C中的慢基数排序

Slow radix sort in C

我必须按升序对数组中的数字进行排序,我的时间复杂度必须为 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; } }

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

分配 space

为了加快排序速度:

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

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

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