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