C++ 基数排序的实现实例代码

C++ 基数排序

　大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是程序设计过程中使用频率极高的算法之一,其输入是一组无序的序列,要求以升序或者降序的方式输出一组有序的序列.对于如二分查找等算法,要求输入是有序的序列,也就是要先排序后查找,由此可见排序算法的重要性.

　　广为人知的排序算法有冒泡排序,还有选择排序,插入排序.高级一些的有快速排序,希尔排序,堆排序,归并排序,基数排序等. 其中时间复杂度为O(n*logn)的算法有快速排序,归并排序和堆排序等,其中快速排序的使用最为广泛.时间复杂度为O(n2)的算法有冒泡排序,选择排序和插入排序等.

　　基数排序是一种非比较的排序算法,它是以桶排序为基础的.它们在现代计算机出现之前,一直被用于老式穿孔卡的排序.

　　基数排序的基本思想是:一共有10个"桶",代表各个数位为0~9.在每个桶上,组织一个优先队列,对于输入的一系列正整数和0,按照个位的大小关系分别进入10个"桶"中.然后遍历每个"桶",按照十位的大小关系进行调整,紧接着是百位,千位.......直到到达最大数的最大位数.结合图例,我们可以理解这个算法:

　　在C++实现中,我用到了队列这一数据结构作为每个"桶"的组织方式,因为取数总是从最下方取,而放入数这是放入"桶"的顶部,这与队列的队头出对,队尾入队的方式相似.对10个"桶"的组织,则采用向量vector.这个程序支持,输入序列一定范围内不限个数,且在int数据类型表示范围内的非负数排序,根据最大数的位数来决定排序趟数.将数据类型从int改为long或者long long ,则可对更大的整数排序.

　　排序函数如下:

 1 vector radix_sort(vector in)
 2 {
 3   vector> bucket(10);      //十个桶为一个向量,每个桶又是一个队列
 4   int max_value = in.at(0);
 5 
 6   for (auto &i : in)
 7   {
 8     if ( i > max_value)
 9max_value = i;
 10   }   //找出输入的最大元素
 11 
 12   int n = 0;
 13 
 14   for (; max_value != 0; max_value /= 10, ++n)
 15     ; //得到最多位数,也即排序趟数
 16 
 17   for (auto &i : in)
 18     bucket.at(0).push(i); //全部放入第一个桶
 19 
 20   int i = 0;    //趟数控制变量
 21   int m = 0;   //提取各个位数有关的控制变量
 22   int k = 0;    //桶数控制变量
 23   int x = 0;    //桶的大小,因动态改变了容器,迭代器会失效,不使用迭代器
 24   int y = 0;    //桶内部控制变量
 25   int j = 0;    
 26   int item = 0;   //桶内元素
 27 
 28   for (; i < n ; ++i)      //趟数循环
 29   {
 30     for ( k = 0; k < 10 ; ++k)    //遍历每个桶
 31     {
 32x = bucket.at(k).size();
 33 
 34if ( !x )
 35  continue;
 36 
 37for (y = 0; y < x ; ++y)   //遍历桶中队列的元素
 38{
 39  item = j = bucket.at(k).front();
 40 
 41  for (m = i; m > 0; --m) //提取出各个位
 42    j /= 10;
 43 
 44  switch (j % 10)     //进入相应的桶
 45  {
 46    case 0:
 47      bucket.at(0).push(item);
 48      break;
 49 
 50    case 1:
 51      bucket.at(1).push(item);
 52      break;
 53 
 54    case 2:
 55      bucket.at(2).push(item);
 56      break;
 57 
 58    case 3:
 59      bucket.at(3).push(item);
 60      break;
 61 
 62    case 4:
 63      bucket.at(4).push(item);
 64      break;
 65 
 66    case 5:
 67      bucket.at(5).push(item);
 68      break;
 69 
 70    case 6:
 71      bucket.at(6).push(item);
 72      break;
 73 
 74    case 7:
 75      bucket.at(7).push(item);
 76      break;
 77 
 78    case 8:
 79      bucket.at(8).push(item);
 80      break;
 81 
 82    case 9:
 83      bucket.at(9).push(item);
 84      break;
 85 
 86    default://异常检测,捕捉与处理
 87      try
 88      {
 89 throw runtime_error("Error!");
 90      }
 91      catch (runtime_error err)
 92      {
 93 cout << err.what() << endl;
 94 exit(EXIT_FAILURE);
 95      }
 96  }
 97 
 98  bucket.at(k).pop();
 99}
100     }
101   }
102 
103   vector out;   //定义一个新的向量,将所有桶的数据收集起来作为最后结果
104 
105   for ( i = 0; i < 10; ++i )
106   {
107     int num = bucket.at(i).size();
108 
109     for (int ai = 0; ai < num; ++ai)
110     {
111out.push_back( bucket.at(i).front() );
112bucket.at(i).pop();
113     }
114   }  //排序结果到一个向量中
115 
116   return out;    //返回这个有序的序列
117 
118 }

    算法要得到正确结果,要注意的是同一个桶的元素的顺序,是从下至上递增的,这是由遍历时从代表0的"桶"开始和从桶中取     元素时是从下取保证的.再有,最后从桶中取出元素时也要注意顺序.