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