鱼C论坛

 找回密码
 立即注册
查看: 3691|回复: 3

[已解决]Radix Sort 问题

[复制链接]
发表于 2016-4-11 04:54:22 | 显示全部楼层 |阅读模式
10鱼币
大家好,这是一个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. void radixsort (long *source, long *temp, long N)
  19. {
  20.      radix (0, N, source, temp);
  21.      radix (1, N, temp, source);
  22.      radix (2, N, source, temp);
  23.      radix (3, N, temp, source);
  24. }

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

  30. long data[25];
  31. long temp[25];

  32. int main (void)
  33. {
  34.      int i;
  35.      make_random(data, 25);
  36.      for (i=0; i<25; i++ )
  37.             cout << data[i] << '\n';
  38.      system("pause");
  39.       radixsort (data, temp, 25);
  40.      for (i=0; i<25; i++ )
  41.             cout << data[i] << '\n';
  42.      system("pause"); return 0;
  43. }
复制代码






最佳答案
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 数组来确定每个元素应当放置的位置。放置一个元素后,对应的索引值会增加一,这样下一个相同的元素就能放置到下一个位置,从而保证了稳定性。这一步是在对数字进行排序。

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

最佳答案

查看完整内容

这是一个基数排序(Radix Sort)的算法,它是一种非比较型整数排序算法。其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这里的实现是一个基于字节的基数排序,它处理32位整数。每个整数被分为4个字节,每个字节包含8位,范围从0到255。 count[((source)>>(byte*8))&0xff]++ 这行代码的作用是为了计算在特定字节位置上,各个可能值(0-255)的出现次数。这里的 ((source)>>(byte*8))&0xff 是用位操作抽取出第 ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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 数组来确定每个元素应当放置的位置。放置一个元素后,对应的索引值会增加一,这样下一个相同的元素就能放置到下一个位置,从而保证了稳定性。这一步是在对数字进行排序。

值得注意的是,这个算法只适用于非负整数。如果有负整数,需要做一些额外的处理才能正确地使用基数排序。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-4-11 13:22:12 | 显示全部楼层
呼叫大boss!@小甲鱼
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-4-11 21:29:06 | 显示全部楼层
围观,学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 17:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表