排序算法之--桶排序/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;>

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<b></b>[k];&gt;

a[j++]=bucket[k][l];

for(j=0; j&lt;10; j++)

b[j]=0;

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274003