比较排序算法的特点就是只有一个维度，也就是说仅仅在需要比较的各个数之间做文章，如果把维度扩大到二维，那么不但要考虑需要比较的数，还要考虑这些数所在的位置，对于数组来讲就是数据的索引，但是一般的说法是桶，维度扩大到二维，空间复杂度必然增加，时间复杂度多半减少，这是一个惯性，一般的比较排序中比如快速排序中，一般不需要额外的内存空间，已经可以达到很高的速度了，效果很好，但是在时间要求比较紧迫的场合，是否可以通过空间再换取一点时间呢？事实证明是可以的，所以就有了非比较排序的排序算法，其中桶排序比较直观，就是将桶按照从小到大或者从大到小的顺序依次排列，然后遍历数组，将数组的数据一个一个的放入到各个桶中，具体怎么放就看规则是什么了，最直观的就是以下的规则：设待排序数中最大的是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;>
if(a[i]>a[max])
max=i;
i=0;
temp=a[max];
while(temp!=0){
temp/=10;
i++;
}
return i;
}
//求一个数第i位的数字（从低到高）
int getBitNum(int num,int i){
while(--i){
num/=10;
}
return num%10;
}
//桶排序主程序
void BucketSort(int a[], int n){
int i, j, max, **bucket=new int*[10]; // i,j用来控制分布元素。
int b[10]={0},k,l,bit; //数组b[10]用来记录每个桶内元素个数
//k,l用来控制元素回收过程
max=getLargest(a,n);
for(i=0; i<10; i++)
bucket[i]=new int[n];
for(i=0; i;>
for(j=0; j;>
bit=getBitNum(a[j],i+1);
bucket[bit][b[bit]]=a[j];
b[bit]++;
}
j=0;
for(k=0;k<10;k++)
for(l=0; l[k];>
a[j++]=bucket[k][l];
}
for(j=0; j<10; j++)
b[j]=0;
}
}
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1274003
