[已解决]Radix Sort 问题

Reggie

大家好，这是一个Radix Sort 问题，就是随机产生25个数字，然后排序，我不太明白 count[((source[ i])>>(byte*8))&0xff]++是什么意思，方括号里边 我可以理解，就是类似于吧0x12345678这个数字分割成了0x12，0x34，0x56，0x78这四个十六进制数字，再把他转化成二进制，但是为什么后面有一个++， 是怎么保存每个数字？ 而且我还不太理解index在这里的作用

#include <iostream>
#include <stdlib.h>
 #include <string.h>
 using namespace std;
void radix (int byte, long N, long *source, long *dest)
 { int i;
   long count[256];
   long index[256];
   memset (count, 0, sizeof (count));
     for (i=0; i<N; i++ )
        count[((source[i])>>(byte*8))&0xff]++;
   index[0]=0;
     for ( i=1; i<256; i++ )
       index[i]=index[i-1]+count[i-1]; // index[4] count[4]
   for ( i=0; i<N; i++ )
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

void radixsort (long *source, long *temp, long N)
{
     radix (0, N, source, temp);
     radix (1, N, temp, source);
     radix (2, N, source, temp);
     radix (3, N, temp, source);
}

void make_random (long *data, long N)
{
     int i; for (i=0; i<N; i++ )
      data[i]=rand()|(rand()<<16);
}

long data[25];
long temp[25];

int main (void)
 {
     int i;
     make_random(data, 25);
     for (i=0; i<25; i++ )
            cout << data[i] << '\n';
     system("pause");
      radixsort (data, temp, 25);
     for (i=0; i<25; i++ )
            cout << data[i] << '\n';
     system("pause"); return 0;
}

最佳答案

月排行榜 / 总排行榜

小甲鱼的二师兄

2016-4-11 04:54:23

这是一个基数排序（Radix Sort）的算法，它是一种非比较型整数排序算法。其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。这里的实现是一个基于字节的基数排序，它处理32位整数。每个整数被分为4个字节，每个字节包含8位，范围从0到255。

count[((source[i ])>>(byte*8))&0xff]++ 这行代码的作用是为了计算在特定字节位置上，各个可能值（0-255）的出现次数。这里的 ((source[i ])>>(byte*8))&0xff 是用位操作抽取出第 byte 个字节的值。然后 count[该值]++ 就是将对应值的计数加一。

接着，index[i ] = index[i-1] + count[i-1] 这行代码计算的是各个值在输出数组中的起始位置。具体来说，如果我们知道值 i-1 的结束位置，那么值 i 的起始位置就是紧接在值 i-1 的结束位置之后。

最后，dest[index[((source[ i])>>(byte*8))&0xff]++] = source[i ] 这行代码负责将源数组中的元素放入到正确的位置。这里使用了 index 数组来确定每个元素应当放置的位置。放置一个元素后，对应的索引值会增加一，这样下一个相同的元素就能放置到下一个位置，从而保证了稳定性。这一步是在对数字进行排序。

值得注意的是，这个算法只适用于非负整数。如果有负整数，需要做一些额外的处理才能正确地使用基数排序。[/i][/i][/i][/i][/i]

跳转到最佳答案楼层

小甲鱼的二师兄

这是一个基数排序（Radix Sort）的算法，它是一种非比较型整数排序算法。其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。这里的实现是一个基于字节的基数排序，它处理32位整数。每个整数被分为4个字节，每个字节包含8位，范围从0到255。

count[((source[i ])>>(byte*8))&0xff]++ 这行代码的作用是为了计算在特定字节位置上，各个可能值（0-255）的出现次数。这里的 ((source[i ])>>(byte*8))&0xff 是用位操作抽取出第 byte 个字节的值。然后 count[该值]++ 就是将对应值的计数加一。

接着，index[i ] = index[i-1] + count[i-1] 这行代码计算的是各个值在输出数组中的起始位置。具体来说，如果我们知道值 i-1 的结束位置，那么值 i 的起始位置就是紧接在值 i-1 的结束位置之后。

最后，dest[index[((source[ i])>>(byte*8))&0xff]++] = source[i ] 这行代码负责将源数组中的元素放入到正确的位置。这里使用了 index 数组来确定每个元素应当放置的位置。放置一个元素后，对应的索引值会增加一，这样下一个相同的元素就能放置到下一个位置，从而保证了稳定性。这一步是在对数字进行排序。

值得注意的是，这个算法只适用于非负整数。如果有负整数，需要做一些额外的处理才能正确地使用基数排序。[/i][/i][/i][/i][/i]

～风介～

呼叫大boss！@小甲鱼

头狼

围观，学习学习