排序算法之--桶排序/radix排序

比较排序算法的特点就是只有一个维度，也就是说仅仅在需要比较的各个数之间做文章，如果把维度扩大到二维，那么不但要考虑需要比较的数，还要考虑这些数所在的位置，对于数组来讲就是数据的索引，但是一般的说法是桶，维度扩大到二维，空间复杂度必然增加，时间复杂度多半减少，这是一个惯性，一般的比较排序中比如快速排序中，一般不需要额外的内存空间，已经可以达到很高的速度了，效果很好，但是在时间要求比较紧迫的场合，是否可以通过空间再换取一点时间呢？事实证明是可以的，所以就有了非比较排序的排序算法，其中桶排序比较直观，就是将桶按照从小到大或者从大到小的顺序依次排列，然后遍历数组，将数组的数据一个一个的放入到各个桶中，具体怎么放就看规则是什么了，最直观的就是以下的规则：设待排序数中最大的是n，那么就准备n个桶，数字i放到第i个桶中，等到所有的数组中的数都放完，依次将桶中的数字输出就可以了，这就是排完序的数组，这个方法的速度很快，可以达到O(n)，但是空间开销可大了去了，难道就不能折中吗？可以的！具体就是桶的数量比最大的待排序数小得多，并且是一个确定的数，靠一种算法将各个数散列到这些桶中，必须保证的小号桶中的最大的数比大号桶中的最小数要小，然后再在各个桶中进行快速排序，堆排序等比较排序，这样时间复杂度和空间复杂度就会跟好的中和，效率自然是很不错的，不会导致极端情况，这种桶排序的一个例子就是radix排序，很多人将二者并列，从某种意义上说，radix排序真的就是桶排序的一个特例，比如对于一个4位的十进制数，最大是9999，那么可以准备一个二维的桶，第一维有9个元素，第二维有待排序数组的元素的个数个元素，设为n，一共扫描m遍，这里的m是4，也就是最大数的位数，首先不考虑高位，先排最低位-个位，如果此时将数据按照桶输出则是个位的排序结果，然后再在此基础上将十位同样排序，一次类推，最终就是一个排序数组。以上是十足的radix排序，但是如果我的第二维不是n个空间的大小呢？比如我就设9999/100个桶，这样桶的数量就节省了，比如0到100的数都会进入同一个桶，以此类推，然后0到100的数可以继续使用更深层次的桶排序，也可以使用比较排序，反正这是一个内部的过程，具体可以看《系统设计---分层，分级，分块》最后给出一个代码(不是我写的)：

注释：

a.对于一维数组的每个值，根据值的个位数，将其放到桶数组的各行中。例如，97放在第7行，3放在第3行，100放在第0行。这称为“分布过程”。

b.在桶数组中逐行循环便利，并把值复制回原始数组。这称为“收集过程”。上述值在一维数组中的新次序是 100、3和97.

c.对随后的每个数位（十位、百位、千位等）重复这个过程。在第二遍排序时，100放在第0行，3放在第0行（因为3没有十位），97放在第9行。收集过程之后，一维数组 中值的顺序为100、3和97.在第三遍排序时，100放在第一行，3放在第0行，97放在第0行（在3之后）。在最后一次收集过程后，原属数组就是有序的了。

//求待排序数种最大的数的位数

int getLargest(int a[], int n){

int i,max,temp;

for(i=1,max=0; i<n i><p>if(a[i]&gt;a[max])</p> <p>max=i;</p> <p>i=0;</p> <p>temp=a[max];</p> <p>while(temp!=0){</p> <p>temp/=10;</p> <p>i++;</p> <p>}</p> <p>return i;</p> <p>}</p> <p>//求一个数第i位的数字（从低到高）</p> <p>int getBitNum(int num,int i){</p> <p>while(--i){</p> <p>num/=10;</p> <p>}</p> <p>return num%10;</p> <p>}</p> <p>//桶排序主程序</p> <p>void BucketSort(int a[], int n){</p> <p>int i, j, max, **bucket=new int*[10]; // i,j用来控制分布元素。</p> <p>int b[10]={0},k,l,bit; //数组b[10]用来记录每个桶内元素个数</p> <p>//k,l用来控制元素回收过程</p> <p>max=getLargest(a,n);</p> <p>for(i=0; i </p> <p>bucket[i]=new int[n];</p> <p>for(i=0; i<max i><p>for(j=0; j<n j><p>bit=getBitNum(a[j],i+1);</p> <p>bucket[bit][b[bit]]=a[j];</p> <p>b[bit]++;</p> <p>}</p> <p>j=0;</p> <p>for(k=0;k </p> <p>for(l=0; l<b l> </b></p> <p>a[j++]=bucket[k][l];</p> <p>}</p> <p>for(j=0; j </p> <p>b[j]=0;</p> <p>}</p> <p>}</p> </n></p></max></p></n>