排序算法之分配排序
羅朝輝（http://m.shnenglu.com/kesalin）
轉載請注明出處
排序是數據處理中經常使用的一種重要運算，在計算機及其應用系統中，花費在排序上的時間在系統運行時間中占有很大比重，其重要性勿需多言。下文將介紹常用的如下排序方法，對它們進行簡單的分析和比較，并提供 C 語言實現。
所謂排序，就是要將一堆記錄，使之按關鍵字遞增(或遞減)次序排列起來。根據排序所采用的策略，可以分為如下五種：
1、插入排序（直接插入排序、希爾排序）
2、交換排序（冒泡排序、快速排序）
3、選擇排序（直接選擇排序、堆排序）
4、歸并排序
5、桶排序（桶排序，基數排序）；
---------------------------------------------------------------------------------
前面講了插入排序，交換排序，選擇排序，歸并排序，下面接著來講桶排序，基數排序。
桶排序和基數排序均屬于分配排序。分配排序的基本思想：排序過程無須比較關鍵字，而是通過用額外的空間來"分配"和"收集"來實現排序，它們的時間復雜度可達到線性階：O(n)。簡言之就是：用空間換時間，所以性能與基于比較的排序才有數量級的提高！
桶排序(Bucket Sort)，也稱箱排序
基本思想：設置若干個箱子，依次掃描待排序的記錄 array[0]，array[1]，…，array[n - 1]，把關鍵字等于 k 的記錄全都裝入到第 k 個箱子里(分配)，然后按序號依次將各非空的箱子里的記錄收集起來，從而完成排序。
桶排序所需要的額外空間取決于關鍵字的個數，若 array[0..n - 1] 中關鍵字的取值范圍是 0 到 m - 1 的整數，則必須設置 m 個箱子。因此箱排序要求關鍵字的類型是有限類型，否則可能要無限個箱子。一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鏈表為宜。
在實現上，桶排序一般采用另外的變種。即：把 [0， m) 劃分為 m 個大小相同的子區間，每一子區間是一個桶。然后將 n 個記錄分配到各個桶中。因為關鍵字序列是均勻分布在[0，m)上的，所以一般不會有很多個記錄落入同一個桶中。由于同一桶中的記錄其關鍵字不盡相同，所以必須采用關鍵字比較的排序方法(通常用插入排序)對各個桶進行排序，然后依次將各非空桶中的記錄收集起來即可。
C 代碼實現：
struct bucket_node 
{
int key;
bucket_node* next;
};
// 取得數組中最大數的位數
int get_max_digital_count(int* array, int length)
{
assert(array && length > 0);
int i = 0;
int max = array[0];
int maxDigitalCount = 1;
for (i = 1; i < length; i++) {
if (max < array[i]) {
max = array[i];
}
}
while ((max / 10) > 0) {
max %= 10;
++maxDigitalCount;
}
return maxDigitalCount;
}
// 取得數 num 中從低到高第 n 位上的數字
int get_ditital_at(int num, int n)
{
while (--n > 0) {
num /= 10;
}
return (num % 10);
}
// 箱/桶排序
//
void bucket_sort(int* array, int length)
{
assert(array && length >= 0);
if (length <= 1) {
return;
}
int i, index;
bucket_node* temp = NULL;
bucket_node bucket[10] = {0, }; // 根據數字個數 0 ~ 9 建立 10 個桶
int count = get_max_digital_count(array, length);
// 建立數據節點
bucket_node* data = (bucket_node*)malloc(length * sizeof(bucket_node));
if (!data) {
printf("Error: out of memory!\n");
return;
}
for (i = 0; i < length; i++) {
data[i].key = array[i];
data[i].next = NULL;
}
// 分配
for (i = 0; i < length; i++) {
index = get_ditital_at(data[i].key, count);
if (bucket[index].next == NULL) {
bucket[index].next = &data[i];
}
else {
temp = &bucket[index];
while (temp->next != NULL && temp->next->key < data[i].key) {
temp = temp->next;
}
data[i].next = temp->next;
temp->next = &data[i];
}
}
// 收集
index = 0;
for (i = 0; i < 10; i++) {
temp = bucket[i].next;
while (temp != NULL) {
array[index++] = temp->key;
temp = temp->next;
}
}
free(data);
}
時間復雜度分析：
桶排序的平均時間復雜度是線性的，即 O(n)。但最壞情況仍有可能是 O(n ^ 2)。
空間復雜度分析：
桶排序只適用于關鍵字取值范圍較小的情況，否則所需箱子的數目 m 太多導致浪費存儲空間和計算時間。
基數排序(Radix Sort)
基本思想：基數排序是對桶排序的改進和推廣。如果說桶排序是一維的基于桶的排序，那么基數排序就是多維的基于桶的排序。我這么說，可能還不是太清楚。比方說：用桶排序對 [0, 30] 之間的數進行排序，那么需要 31 個桶，分配一次，收集一次，完成排序；那么基數排序則只需要 0 - 9 總共 10 個桶（即關鍵字為數字 0 - 9），依次進行個位和十位的分配和收集從而完成排序。
C 代碼實現：
// 基數排序
//
void radix_sort(int* array, int length)
{
assert(array && length >= 0);
if (length <= 1) {
return;
}
const int buffer_size = length * sizeof(int);
int i, k, count, index;
int bucket[10] = {0, }; // 根據數字個數 0 ~ 9 建立 10 個桶
int* temp = (int*)malloc(buffer_size);
if (!temp) {
printf("Error: out of memory!\n");
return;
}
count = get_max_digital_count(array, length);
for (k = 1; k <= count; ++k) {
memset(bucket, 0, 10 * sizeof(int));
// 統計各桶中元素的個數
for (i = 0; i < length; ++i) {
index = get_ditital_at(array[i], k);
++bucket[index];
}
// 為每個記錄創建索引下標
for (i = 1; i < 10; ++i) {
bucket[i] += bucket[i - 1];
}
// 按索引下標順序排列
for (i = length - 1; i >= 0; --i) {
index = get_ditital_at(array[i], k);
assert(bucket[index] - 1 >= 0);
temp[--bucket[index]] = array[i];
}
// 一趟桶排序完畢，拷貝結果
memcpy(array, temp, buffer_size);
#ifdef DEBUG_SORT
debug_print(" 第 %d 趟排序：", k);
for (i = 0; i < length; ++i) {
debug_print("%d ", array[i]);
}
debug_print("\n");
#endif
}
free(temp);
}
時間復雜度分析：
基數排序的時間負責度為 O(n)。
空間復雜度：
基數排序所需的輔助存儲空間為 O(n + r * d)，其中 r 為記錄中關鍵字分量的最大個數，d 為關鍵字的個數。比如說：待排序為 0 - 999，那么分量的最大個數為 3，關鍵字的個數為 10（0 - 9）。
補充：
基數排序是穩定的。
若排序文件不是以數組 array 形式給出，而是以單鏈表形式給出(此時稱為鏈式的基數排序)，則可通過修改出隊和入隊函數使表示箱子的鏈隊列無須分配結點空間，而使用原鏈表的結點空間。人隊出隊操作亦無需移動記錄而僅需修改指針。雖然這樣一來節省了一定的時間和空間，但算法要復雜得多，且時空復雜度就其數量級而言并未得到改觀。
=======================================================================================
測試：
在前文《排序算法之插入排序》測試代碼的基礎上添加兩行代碼即可：
{"桶/箱排序", bucket_sort},
{"基數排序", radix_sort},
測試結果：
=== 桶/箱排序 ===
original: 65 32 49 10 8 72 27 42 18 58 91
sorted: 8 10 18 27 32 42 49 58 65 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
sorted: 0 1 2 3 4 5 6 7 8 9 10
=== 基數排序 ===
original: 65 32 49 10 8 72 27 42 18 58 91
第 1 趟排序：10 91 32 72 42 65 27 8 18 58 49
第 2 趟排序：8 10 18 27 32 42 49 58 65 72 91
sorted: 8 10 18 27 32 42 49 58 65 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
第 1 趟排序：10 0 1 2 3 4 5 6 7 8 9
第 2 趟排序：0 1 2 3 4 5 6 7 8 9 10
sorted: 0 1 2 3 4 5 6 7 8 9 10