引言
注：由於沒有啟用任何公式編輯器，為表示方便：以下涉及時間復雜度表示時，其漸近符號用以下符號代替：
先來看一個定理：任意一個比較排序算法在最壞情況下，都需要做 $(nlgn)次的比較。其可用決策樹模型加以證明，詳見：《算法導論》第8章8.1節。
該定理指出了比較排序的時間復雜度下界，即沒有比較更少的了。
故以下介紹的三種算法均不是基於比較的排序算法，其均對輸入數據作了某種假設，即利用了具體數據的特點。
一、計數排序
1、問題描述：假設數組中的n個元素中的每一個都是介於0到k之間的整數，對其進行排序。此處k為某個正整數。
2、基本思想：對每一個輸入元素x，利用它的所屬范圍大小為[0, k] ,確定出數組中小於x 的元素個數。由於x為正整數，則可以直接把x直接放到它在最終輸出數組中的位置上。
3、算法描述：
輸入：A[1...n], 輸入數組；C[0...k]，提供臨時存儲區，初值：0 ---O(k)
輸出：B[1...n]，存放排序結果
（1）求出輸入數組A[]1...n]中，其值等於A[j]的元素個數，存放於對應的C[1...k]中：C[A[i]] = C[A[i]] + 1 ---O(n)
（2）求出輸入數組A[]1...n]中，其值小於或等於A[j]的元素個數，迭代地存放於對應的C[1...k]中：C[j] = C[j-1] + C[j] ---O(K)
（3）經過前兩步之後，C[i]中的值表示為：小於等於 i 的元素個數，即 為 i 在A[1...n]中的最終位置，將其存放於B[1...n]中：B[C[A[j]]] = A[j], C[A[j]] = C[A[j]] - 1 （有可能存在想相等的元素） --- O(n)
4、時間復雜度：O(k) + O(n) + O(k) + O(n)，則總的運行時間為：@(k+n)，在實踐中，當 k=O(n)時，其運行時間即為：@(n).
5、算法實現：
[cpp]
#include <stdio.h>
const int K = 5;
const int N = 6;
int input[N+1] = {-1, 2, 3, 4, 2 ,1, 5};
int output[N+1];
int count[K]={0};
void print(int array[], int n)
{
for(int i = 1; i <=n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
void countSort(int input[], int output[], int n)
{
int i;
for(i = 1; i <= n; i++)
{//equal to input[i]
count[input[i]] = count[input[i]] +1;
}
for(i = 1; i <= K; i++)
{//less ro equal to i
count[i] = count[i-1] + count[i];
}
for(i = n; i >= 1; i--) //form large to small to make sorting stable
{
output[count[input[i]]] = input[i];
count[input[i]]--;
}
}
int main()
{
countSort(input, output, N);
print(output, N);
return 0;
}
#include <stdio.h>
const int K = 5;
const int N = 6;
int input[N+1] = {-1, 2, 3, 4, 2 ,1, 5};
int output[N+1];
int count[K]={0};
void print(int array[], int n)
{
for(int i = 1; i <=n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
void countSort(int input[], int output[], int n)
{
int i;
for(i = 1; i <= n; i++)
{//equal to input[i]
count[input[i]] = count[input[i]] +1;
}
for(i = 1; i <= K; i++)
{//less ro equal to i
count[i] = count[i-1] + count[i];
}
for(i = n; i >= 1; i--) //form large to small to make sorting stable
{
output[count[input[i]]] = input[i];
count[input[i]]--;
}
}
int main()
{
countSort(input, output, N);
print(output, N);
return 0;
}
二、基數排序
1、問題描述：給定n個d位數，每一位可能的取值有k中，對其進行排序。如，4個三位數：123，367,124,756，此時n=4, d=3，k值為10.
2、基本思想：首先按最低有效位數字進行排序，收集結果；然後按次低位有效位數字排序，收集其結果，依次類推，重復這個過程，直到對所有的d位數字都進行 了排序。
看個例子（來自算法導論8.3的示例,P100）：
注意：對每一位的排序必須是一個穩定的排序，否則排序可能不正確。如上圖在對最高位排序時，起初436在457的前面，由於最高位都是4，故此次排序兩個數的最高位相等，如果不是穩定的排序，結果457可能會排到436的前面，這樣結果就不對了。而穩定的排序則可以保證排完後，436仍然在457的前面。
3、算法描述：
輸入數組：A[1...n]
RADIX-SORT(A, d)
for i <- 1 to d
do use a stable sort to sort array A on digit i //可以選擇計數排序
4、時間復雜度：由一中的計數排序可知，對每一位的排序時間為：@(k+n)，此處共執行d遍，故時間復雜度：@(d*(k+n))，當d為常數、k=O(n)時，基數排序有線性運行時間：@(n)。更一般且更具體的分析可以參加《算法導論》的引理8.3和8.4，P101，其詳細分析了：如何將每個關鍵字分解成若干位以及那些情況下時間復雜度最佳。此處只介紹一些結論與如何實現之。
5、算法實現：
[cpp]
#include <stdio.h>
#include <math.h>
const int N = 7;
const int D = 3;
const int K = 10;
int count[K] = {0};
//int input[N+1] = {-1, 329, 457, 657, 839, 436, 720, 355};
int output[D+1][N+1]={{-1, 329, 457, 657, 839, 436, 720, 355}};
void print(int array[], int n)
{
for(int i = 1; i <=n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
int getDigit(int number, int d)
{
if(d > D)return -1;
return number%(int)pow(10,d) / (int)pow(10,d-1);
}
void countSort(int input[], int output[], int n, int d)
{
int i;
int digit;
for(i = 1; i <= n; i++)
{
digit = getDigit(input[i],d);
count[digit] = count[digit] +1;
}
for(i = 1; i <= K; i++)
{
count[i] = count[i-1] + count[i];
}
for(i = n; i >= 1; i--) //form large to small to make sorting stable
{
digit = getDigit(input[i],d);
output[count[digit]] = input[i];
count[digit]--;
}
}
void initDataStruct(int count[])
{
for(int i= 0; i < K; i++)
{
count[i] = 0;
}
}
void radixSort(int output[][N+1], int n, int d)
{
for(int i = 1; i <= d; i++)
{
countSort(output[i-1], output[i], n, i);
initDataStruct(count);
}
}
int main()
{
radixSort(output, N, D);
print(output[D], N);
return 0;
}
#include <stdio.h>
#include <math.h>
const int N = 7;
const int D = 3;
const int K = 10;
int count[K] = {0};
//int input[N+1] = {-1, 329, 457, 657, 839, 436, 720, 355};
int output[D+1][N+1]={{-1, 329, 457, 657, 839, 436, 720, 355}};
void print(int array[], int n)
{
for(int i = 1; i <=n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
int getDigit(int number, int d)
{
if(d > D)return -1;
return number%(int)pow(10,d) / (int)pow(10,d-1);
}
void countSort(int input[], int output[], int n, int d)
{
int i;
int digit;
for(i = 1; i <= n; i++)
{
digit = getDigit(input[i],d);
count[digit] = count[digit] +1;
}
for(i = 1; i <= K; i++)
{
count[i] = count[i-1] + count[i];
}
for(i = n; i >= 1; i--) //form large to small to make sorting stable
{
digit = getDigit(input[i],d);
output[count[digit]] = input[i];
count[digit]--;
}
}
void initDataStruct(int count[])
{
for(int i= 0; i < K; i++)
{
count[i] = 0;
}
}
void radixSort(int output[][N+1], int n, int d)
{
for(int i = 1; i <= d; i++)
{
countSort(output[i-1], output[i], n, i);
initDataStruct(count);
}
}
int main()
{
radixSort(output, N, D);
print(output[D], N);
return 0;
}
三、桶排序
1、問題描述：假設輸入數組有一個隨機過程產生，該過程將元素均勻地分布在區間 [0, 1)上，對這個輸入數組進行排序
2、基本思想：類似於散列表中解決散列沖突的拉鏈法，一個桶本質就是一個鏈表，將相同關鍵字的元素會被放入同一個桶中。由於輸入數組中的元素均勻且獨立均勻分布在 [0, 1)上，所以一般不會有很多個元素被分到同一個桶中去。散列完成後，先對各個桶中的元素進行排序，然後按次序把各桶中的元素收集出來即得到一個有序的數組。
3、算法描述：
輸入：A[1...n]；B[0...n-1]：輔助數組鏈表，用於散列元素
輸出：排序好的A[1...n]
（1）把區間 [0, 1) 劃分成 n個相同大小的子區間，或稱為桶（可用輔助數組鏈表B[0...n-1) 實現之）。
（2）已知，散列函數為：f(x) = floor(n*x) ， 向下取整，則數組元素A[i] 分配至 桶（鏈表）B[floor(n*A[i])]中 ---@(n)
（3）分別對每個桶B[i]中的元素進行排序（可用插入排序實現之） ---n*O(2-1/n)
（4）按次序收集各桶中的結果。
4、時間復雜度：根據3中的算法描述部分可知，除了第（3）步外，其他各部分在最壞情況下的時間都是O(n)。運用數理統計的知識可以求得，第（3）步中的對每個桶進行排序，運行時間的期望值為：2-1/n（詳見：《算法導論》8.4節,P103），則第（3）步的總時間：n*(2-1/n)，故桶排序的期望運行時間：@(n) + n*(2-1/n) =@(n)
5、算法實現：
[cpp]
#include <stdio.h>
#include <math.h>
const int N =10;
double input[N+1] = {-1, 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
typedef struct BucketNode
{
double data;
struct BucketNode* next;
}* bucketList, bucketNode;
bucketList bucketArr[N];
void print(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketNode* pb = bucketArr[i];
while(pb)
{
printf("%e ", pb->data);
pb = pb->next;
}
printf("\n");
}
printf("\n");
}
void initBucketList(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketArr[i] = NULL;
}
}
bool insertBucketWithSorting(bucketList& bucket, double data)
{//sorting while inserting
bucketNode* pb = new bucketNode;
if(NULL == pb)
return false;
pb->data = data;
if(NULL == bucket || pb->data < bucket->data)
{//insert before the first element
pb->next = bucket;
bucket = pb;
return true;
}
bucketNode* ptemp = bucket;
bucketNode* ptempn = bucket->next;
while(ptempn)
{//insert after the first element(that is in the middle)
if(pb->data < ptempn->data)
{
pb->next = ptempn;
ptemp->next = pb;
break;
}
ptemp = ptempn;
ptempn = ptempn->next;
}
if(NULL == ptempn)
{//insert after the last element
ptemp->next = pb;
pb->next = NULL;
}
return true;
}
void destroyBucketList(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
while(bucketArr[i]!= NULL)
{
bucketNode* pb = bucketArr[i];
bucketArr[i] = bucketArr[i]->next ;
delete pb;
pb = NULL;
}
}
}
void bucketSort(double input[], bucketList bucketArr[],int n)
{
for(int i = 1; i <= n; i++)
{
int index = (int)floor(input[i]*n);
insertBucketWithSorting(bucketArr[index], input[i]);
}
}
int main()
{
initBucketList(bucketArr);
bucketSort(input, bucketArr, N);
print(bucketArr);
destroyBucketList(bucketArr);
return 0;
}
#include <stdio.h>
#include <math.h>
const int N =10;
double input[N+1] = {-1, 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
typedef struct BucketNode
{
double data;
struct BucketNode* next;
}* bucketList, bucketNode;
bucketList bucketArr[N];
void print(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketNode* pb = bucketArr[i];
while(pb)
{
printf("%e ", pb->data);
pb = pb->next;
}
printf("\n");
}
printf("\n");
}
void initBucketList(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketArr[i] = NULL;
}
}
bool insertBucketWithSorting(bucketList& bucket, double data)
{//sorting while inserting
bucketNode* pb = new bucketNode;
if(NULL == pb)
return false;
pb->data = data;
if(NULL == bucket || pb->data < bucket->data)
{//insert before the first element
pb->next = bucket;
bucket = pb;
return true;
}
bucketNode* ptemp = bucket;
bucketNode* ptempn = bucket->next;
while(ptempn)
{//insert after the first element(that is in the middle)
if(pb->data < ptempn->data)
{
pb->next = ptempn;
ptemp->next = pb;
break;
}
ptemp = ptempn;
ptempn = ptempn->next;
}
if(NULL == ptempn)
{//insert after the last element
ptemp->next = pb;
pb->next = NULL;
}
return true;
}
void destroyBucketList(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
while(bucketArr[i]!= NULL)
{
bucketNode* pb = bucketArr[i];
bucketArr[i] = bucketArr[i]->next ;
delete pb;
pb = NULL;
}
}
}
void bucketSort(double input[], bucketList bucketArr[],int n)
{
for(int i = 1; i <= n; i++)
{
int index = (int)floor(input[i]*n);
insertBucketWithSorting(bucketArr[index], input[i]);
}
}
int main()
{
initBucketList(bucketArr);
bucketSort(input, bucketArr, N);
print(bucketArr);
destroyBucketList(bucketArr);
return 0;
}
