[关闭]
@skyword 2017-06-03T06:11:37.000000Z 字数 2040 阅读 151

第十二次上机报告


问题描述

基数排序算法设计,并测试

处理思路

基数排序主要用于对整数排序
对于k进制m位整数序列,可以用基数排序的方式来排序,其中不足m位的整数补足前导0
定义k个顺序队列,例如对于十进制整数排序,定义十个队列
对于m位序列,执行m次排序,对于第i次排序
按照序列中从左到右的次序取数,若该数的第i位为t,则将该数入队列q[t],将所有数按此方法入队。
然后再按照q[0]到q[k]的次序将整数逐步出队,存储回到原数组中,完成一次排序
重复k次即可

实际上是将全部整数从低位到高位逐步排序,最终完成整体排序。
深入一步说,对于要排序的元素定义了一个有限维线性空间,维度为整数的最大位数,所谓定义k个队列就是选取了线性空间的一组基。基内元素是线性无关的,这是k次排序互不相关的原因。
从这个角度上讲,基数排序可以扩展到有限位小数排序,位数增多而已。
对于抽象数据类型的排序,若是能定义对应的有限维空间,并选择对应的一组基,还能用某种方式(例如hash)转化成数据结构实现,那么基数排序应该也可以应用。
队列实现是为了保证基数排序的稳定性,放到同一个桶里的整数,先进先出,就以为着当前排序特征相同的元素,排序结束之后的次序和原次序一致。

代码设计

队列结构直接使用STL标准类queue

程序代码

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <queue>
  4. using namespace std;
  5. #define N 50
  6. queue<int>q[10];
  7. int n,a[N];
  8. int po10[11];
  9. void init()
  10. {
  11. po10[0] = 1;
  12. for(int i = 1; i <= 10; i++)
  13. {
  14. po10[i] = po10[i-1]*10;
  15. }
  16. }
  17. int getdig(int n)
  18. {
  19. int dig = 0;
  20. while(n)
  21. {
  22. dig++;
  23. n/=10;
  24. }
  25. return dig;
  26. }
  27. int main()
  28. {
  29. init();
  30. cout<<"Input amounts of numbers in the array.(at most 50 numbers)"<<endl;
  31. cin>>n;
  32. cout<<"Input "<<n<<" integers divided by a single space(at most 1e10): "<<endl;
  33. int dig = 0;
  34. for(int i = 0; i < n; i++)
  35. {
  36. cin>>a[i];
  37. dig = max(dig, getdig(a[i]));
  38. }
  39. for(int i = 1; i <= dig; i++)//i-th barrel-sort.
  40. {
  41. for(int j = 0; j < n; j++)
  42. {
  43. int now = a[j];
  44. int k = (int)(now / po10[i-1]) - 10 * (int)(now / po10[i]);
  45. if(k < 0 )k=0;
  46. q[k].push(now);
  47. }
  48. int index = 0;
  49. for(int j = 0; j < 10; j++)
  50. {
  51. while(!q[j].empty())
  52. {
  53. int now = q[j].front();
  54. q[j].pop();
  55. a[index++] = now;
  56. }
  57. }
  58. printf("******\n");
  59. printf("Barrel Sort #%d: \n",i);
  60. for(int k = 0; k < n; k++)
  61. {
  62. printf("%d ",a[k]);
  63. }
  64. printf("\n");
  65. }
  66. printf("The final result: \n");
  67. for(int i = 0; i < n; i++)
  68. cout<<a[i]<<" ";
  69. cout<<endl;
  70. }

测试效果

15个整数排序:将每次排序的结果也输出出来

  1. Input amounts of numbers in the array.(at most 50 numbers)
  2. 15
  3. Input 15 integers divided by a single space(at most 1e10):
  4. 23 122 033 0 1900 324353 877 254 5905 32 33 122 033 877 899
  5. ******
  6. Barrel Sort #1:
  7. 0 1900 122 32 122 23 33 324353 33 33 254 5905 877 877 899
  8. ******
  9. Barrel Sort #2:
  10. 0 1900 5905 122 122 23 32 33 33 33 324353 254 877 877 899
  11. ******
  12. Barrel Sort #3:
  13. 0 23 32 33 33 33 122 122 254 324353 877 877 899 1900 5905
  14. ******
  15. Barrel Sort #4:
  16. 0 23 32 33 33 33 122 122 254 877 877 899 1900 324353 5905
  17. ******
  18. Barrel Sort #5:
  19. 0 23 32 33 33 33 122 122 254 877 877 899 1900 5905 324353
  20. ******
  21. Barrel Sort #6:
  22. 0 23 32 33 33 33 122 122 254 877 877 899 1900 5905 324353
  23. The final result:
  24. 0 23 32 33 33 33 122 122 254 877 877 899 1900 5905 324353
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注