Radix Sort 问题
大家好，这是一个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;
long index;
memset (count, 0, sizeof (count));
for (i=0; i<N; i++ )
count[((source)>>(byte*8))&0xff]++;
index=0;
for ( i=1; i<256; i++ )
index=index+count; // index count
for ( i=0; i<N; i++ )
dest)>>(byte*8))&0xff]++] = source;
}
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=rand()|(rand()<<16);
}
long data;
long temp;
int main (void)
{
int i;
make_random(data, 25);
for (i=0; i<25; i++ )
cout << data << '\n';
system("pause");
radixsort (data, temp, 25);
for (i=0; i<25; i++ )
cout << data << '\n';
system("pause"); return 0;
}
这是一个基数排序（Radix Sort）的算法，它是一种非比较型整数排序算法。其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。这里的实现是一个基于字节的基数排序，它处理32位整数。每个整数被分为4个字节，每个字节包含8位，范围从0到255。
count[((source)>>(byte*8))&0xff]++ 这行代码的作用是为了计算在特定字节位置上，各个可能值（0-255）的出现次数。这里的 ((source)>>(byte*8))&0xff 是用位操作抽取出第 byte 个字节的值。然后 count[该值]++ 就是将对应值的计数加一。
接着，index = index + count 这行代码计算的是各个值在输出数组中的起始位置。具体来说，如果我们知道值 i-1 的结束位置，那么值 i 的起始位置就是紧接在值 i-1 的结束位置之后。
最后，dest)>>(byte*8))&0xff]++] = source 这行代码负责将源数组中的元素放入到正确的位置。这里使用了 index 数组来确定每个元素应当放置的位置。放置一个元素后，对应的索引值会增加一，这样下一个相同的元素就能放置到下一个位置，从而保证了稳定性。这一步是在对数字进行排序。
值得注意的是，这个算法只适用于非负整数。如果有负整数，需要做一些额外的处理才能正确地使用基数排序。 呼叫大boss！{:10_256:}@小甲鱼 围观，学习学习
页:
[1]