[已解决]Radix Sort 问题

Reggie

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

1. #include <iostream>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. using namespace std;
   
5. void radix (int byte, long N, long *source, long *dest)
   
6. { int i;
   
7.    long count[256];
   
8.    long index[256];
   
9.    memset (count, 0, sizeof (count));
   
10.      for (i=0; i<N; i++ )
    
11.         count[((source[i])>>(byte*8))&0xff]++;
    
12.    index[0]=0;
    
13.      for ( i=1; i<256; i++ )
    
14.        index[i]=index[i-1]+count[i-1]; // index[4] count[4]
    
15.    for ( i=0; i<N; i++ )
    
16.     dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
    
17. }
    
18. 
    
19. void radixsort (long *source, long *temp, long N)
    
20. {
    
21.      radix (0, N, source, temp);
    
22.      radix (1, N, temp, source);
    
23.      radix (2, N, source, temp);
    
24.      radix (3, N, temp, source);
    
25. }
    
26. 
    
27. void make_random (long *data, long N)
    
28. {
    
29.      int i; for (i=0; i<N; i++ )
    
30.       data[i]=rand()|(rand()<<16);
    
31. }
    
32. 
    
33. long data[25];
    
34. long temp[25];
    
35. 
    
36. int main (void)
    
37. {
    
38.      int i;
    
39.      make_random(data, 25);
    
40.      for (i=0; i<25; i++ )
    
41.             cout << data[i] << '\n';
    
42.      system("pause");
    
43.       radixsort (data, temp, 25);
    
44.      for (i=0; i<25; i++ )
    
45.             cout << data[i] << '\n';
    
46.      system("pause"); return 0;
    
47. }

复制代码

最佳答案

月排行榜 / 总排行榜

小甲鱼的二师兄

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！@小甲鱼

头狼

围观，学习学习