排序（三）

桶排序

桶排序工作的原理是將數組分到有限數量的桶里。每個桶再個別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ(n)）。

桶排序的缺點是需要知道給定數組的最大值和最小值，然後建立內存空間。有時這個內存空間可能會非常大。

// Demonstrationn#include <iostream>nusing namespace std;nint main(){n int buckets[100];n int n;n cin >> n;n for(int i = 0; i < n; i++){n int t;n cin >> t;n buckets[t]++;n }n for(int i = 0; i < 100; i++){n for(int j = 0; j < buckets[i]; j++)n cout << i << " ";n }n return 0;n}n

基數排序

基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片製表機上的貢獻。

它是這樣實現的：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

原理類似桶排序，這裡總是需要10個桶（如果不是10進位，那麼桶數量有所不同），多次使用。

首先以個位數的值進行裝桶，暫時忽視十位數。

例如：簡單點五個數字，待排序數組[62,14,59,88,16]

分配10個桶，桶編號為0-9，以個位數數字為桶編號依次入桶，變成下邊這樣：

數據 | 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |

桶編號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

（非等寬字體差評）

將桶里的數字順序取出來，輸出結果：[62,14,16,88,59]

再次入桶，不過這次以十位數（倒數第二位）的數字為準，進入相應的桶，變成下邊這樣：

由於前邊做了個位數的排序，所以當十位數相等時，個位數字是由小到大的順序入桶的，就是說，入完桶還是有序：

數據 | 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |

桶編號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

然後輸出結果：[14,16,59,62,88]

然後循環，直到所有位都被處理完畢。在這裡因為只有兩位，循環就結束了。

放代碼：

int maxbit(int data[], int n){ //輔助函數，求數據的最大位數n int d = 1; //保存最大的位數n int p = 10;n for(int i = 0; i < n; ++i)n {n while(data[i] >= p)n {n p *= 10;n ++d;n }n }n return d;n}nvoid radixsort(int data[], int n){n int d = maxbit(data, n);n int *tmp = newint[n];n int *count = newint[10]; //計數器n int i, j, k;n int radix = 1;n for(i = 1; i <= d; i++){ //進行d次排序n for(j = 0; j < 10; j++)n count[j] = 0; //每次分配前清空計數器n for(j = 0; j < n; j++){n k = (data[j] / radix) % 10; //統計每個桶中的記錄數n count[k]++;n }n for(j = 1; j < 10; j++)n count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶n for(j = n - 1; j >= 0; j--){n k = (data[j] / radix) % 10;n tmp[count[k] - 1] = data[j];n count[k]--;n }n for(j = 0; j < n; j++) //將臨時數組的內容複製到data中n data[j] = tmp[j];n radix = radix * 10;n }n delete[]tmp;n delete[]count;n}n

上面的基數排序演算法是LSD的，從最右面開始。這是一個穩定的排序演算法。

如果使用MSD的基數排序，從最高位開始，那麼這不是一個穩定的排序演算法。