区间排序算法的实现,代码C++,排序算法的问题假设含假设含n个数据元素的序列中,所有关键字为介于个数据元素的序列中,所有关键字为介于u和w之间的整数,且其中很多关键字值是相同.则

Question

区间排序算法的实现,代码C++,排序算法的问题
假设含 假设含 n个数据元素的序列中,所有关键字为介于 个数据元素的序列中,所有关键字为介于 u和 w之间的整数,且其 中很多关键字值是相同.则可按如下方法进行排序：设数组 number[0..w-u]且令 number[i] 统计关 键字 等于 整数 u+i的数据元素个数,然后按 number [ ]的值重排序列以达到有序.

Answer 1

这不就类似于桶排序么,只不过桶的大小为序列的最大值减去最小值+1而已.

伪代码如下：

 void bucketsort(int * Input,int len)
 {
     int u,w;
     u= min in Input;
     w= max in Input;
     int *bucket=new int[w-u+1];
     for(int i=0;i          bucket[i]=0;
     for(int i=0;i          bucket[Input[i]-u]++;
     // print result;
     for(int i=0;i         while(bucket[i])
         {
             cout<             bucket[i]--;
 }