Beyond the Void
BYVoid
三種線性排序算法 計數排序、桶排序與基數排序
本文正體字版由OpenCC轉換

[非基於比較的排序]

在計算機科學中,排序是一門基礎的算法技術,許多算法都要以此作爲基礎,不同的排序算法有着不同的時間開銷和空間開銷。排序算法有非常多種,如我們最常用的快速排序和堆排序等算法,這些算法需要對序列中的數據進行比較,因爲被稱爲基於比較的排序

基於比較的排序算法是不能突破O(NlogN)的。簡單證明如下:

N個數有N!個可能的排列情況,也就是說基於比較的排序算法的判定樹有N!個葉子結點,比較次數至少爲log(N!)=O(NlogN)(斯特林公式)。

非基於比較的排序,如計數排序,桶排序,和在此基礎上的基數排序,則可以突破O(NlogN)時間下限。但要注意的是,非基於比較的排序算法的使用都是有條件限制的,例如元素的大小限制,相反,基於比較的排序則沒有這種限制(在一定範圍內)。但並非因爲有條件限制就會使非基於比較的排序算法變得無用,對於特定場合有着特殊的性質數據,非基於比較的排序算法則能夠非常巧妙地解決。

本文着重介紹三種線性的非基於比較的排序算法:計數排序、桶排序與基數排序。

[計數排序]

首先從計數排序(Counting Sort)開始介紹起,假設我們有一個待排序的整數序列A,其中元素的最小值不小於0,最大值不超過K。建立一個長度爲K的線性表C,用來記錄不大於每個值的元素的個數。

算法思路如下:

  1. 掃描序列A,以A中的每個元素的值爲索引,把出現的個數填入C中。此時C[i]可以表示A中值爲i的元素的個數。
  2. 對於C從頭開始累加,使C[i]<-C[i]+C[i-1]。這樣,C[i]就表示A中值不大於i的元素的個數
  3. 按照統計出的值,輸出結果。

由線性表C我們可以很方便地求出排序後的數據,定義B爲目標的序列,Order[i]爲排名第i的元素在A中的位置,則可以用以下方法統計。

/*
 * Problem: Counting Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:27
 * State: Solved
 * Memo: 計數排序
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
	int *C=new int[K+1];
	int i;
	memset(C,0,sizeof(int)*(K+1));
	for (i=1;i<=N;i++) //把A中的每個元素分配
		C[A[i]]++;
	for (i=2;i<=K;i++) //統計不大於i的元素的個數
		C[i]+=C[i-1];
	for (i=N;i>=1;i--)
	{
		B[C[A[i]]]=A[i]; //按照統計的位置,將值輸出到B中,將順序輸出到Order中
		Order[C[A[i]]]=i;
		C[A[i]]--;
	}
}
int main()
{
	int *A,*B,*Order,N=15,K=10,i;
	A=new int[N+1];
	B=new int[N+1];
	Order=new int[N+1];
	for (i=1;i<=N;i++)
		A[i]=rand()%K+1; //生成1..K的隨機數
	printf("Before CS:\n");
	for (i=1;i<=N;i++)
		printf("%d ",A[i]);
	CountingSort(A,B,Order,N,K);
	printf("\nAfter CS:\n");
	for (i=1;i<=N;i++)
		printf("%d ",B[i]);
	printf("\nOrder:\n");
	for (i=1;i<=N;i++)
		printf("%d ",Order[i]);
	return 0;
}

程序運行效果如下:

Before CS:
2 8 5 1 10 5 9 9 3 5 6 6 2 8 2
After CS:
1 2 2 2 3 5 5 5 6 6 8 8 9 9 10
Order:
4 1 13 15 9 3 6 10 11 12 2 14 7 8 5

顯然地,計數排序的時間複雜度爲O(N+K),空間複雜度爲O(N+K)。當K不是很大時,這是一個很有效的線性排序算法。更重要的是,它是一種穩定排序算法,即排序後的相同值的元素原有的相對位置不會發生改變(表現在Order上),這是計數排序很重要的一個性質,就是根據這個性質,我們才能把它應用到基數排序。

[桶排序]

可能你會發現,計數排序似乎饒了點彎子,比如當我們剛剛統計出C,C[i]可以表示A中值爲i的元素的個數,此時我們直接順序地掃描C,就可以求出排序後的結果。的確是這樣,不過這種方法不再是計數排序,而是桶排序(Bucket Sort),確切地說,是桶排序的一種特殊情況。

用這種方法,可以很容易寫出程序,比計數排序還簡單,只是不能求出穩定的Order。

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:32
 * State: Solved
 * Memo: 桶排序特殊實現
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void BucketSort(int *A,int *B,int N,int K)
{
	int *C=new int[K+1];
	int i,j,k;
	memset(C,0,sizeof(int)*(K+1));
	for (i=1;i<=N;i++) //把A中的每個元素按照值放入桶中
		C[A[i]]++;
	for (i=j=1;i<=K;i++,j=k) //統計每個桶元素的個數,並輸出到B
		for (k=j;k<j+C[i];k++)
			B[k]=i;
}
int main()
{
	int *A,*B,N=1000,K=1000,i;
	A=new int[N+1];
	B=new int[N+1];
	for (i=1;i<=N;i++)
		A[i]=rand()%K+1; //生成1..K的隨機數
	BucketSort(A,B,N,K);
	for (i=1;i<=N;i++)
		printf("%d ",B[i]);
	return 0;
}

這種特殊實現的方式時間複雜度爲O(N+K),空間複雜度也爲O(N+K),同樣要求每個元素都要在K的範圍內。更一般的,如果我們的K很大,無法直接開出O(K)的空間該如何呢?

首先定義桶,桶爲一個數據容器,每個桶存儲一個區間內的數。依然有一個待排序的整數序列A,元素的最小值不小於0,最大值不超過K。假設我們有M個桶,第i個桶Bucket[i]存儲i*K/M至(i+1)*K/M之間的數,有如下桶排序的一般方法:

  1. 掃描序列A,根據每個元素的值所屬的區間,放入指定的桶中(順序放置)。
  2. 對每個桶中的元素進行排序,什麼排序算法都可以,例如快速排序。
  3. 依次收集每個桶中的元素,順序放置到輸出序列中。

對該算法簡單分析,如果數據是期望平均分佈的,則每個桶中的元素平均個數爲N/M。如果對每個桶中的元素排序使用的算法是快速排序,每次排序的時間複雜度爲O(N/M*log(N/M))。則總的時間複雜度爲O(N)+O(M)*O(N/M*log(N/M)) = O(N+ N*log(N/M)) = O(N + N*logN - N*logM)當M接近於N是,桶排序的時間複雜度就可以近似認爲是O(N)的。就是桶越多,時間效率就越高,而桶越多,空間卻就越大,由此可見時間和空間是一個矛盾的兩個方面。

桶中元素的順序放入和順序取出是有必要的,因爲這樣可以確定桶排序是一種穩定排序算法,配合基數排序是很好用的。

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo: 桶排序一般實現
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct linklist
{
	linklist *next;
	int value;
	linklist(int v,linklist *n):value(v),next(n){}
	~linklist() {if (next) delete next;}
};
inline int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
/*
爲了方便,我把A中元素加入桶中時是倒序放入的,而收集取出時也是倒序放入序列的,所以不違背穩定排序。
*/
void BucketSort(int *A,int *B,int N,int K)
{
	linklist *Bucket[101],*p;//建立桶
	int i,j,k,M;
	M=K/100;
	memset(Bucket,0,sizeof(Bucket));
	for (i=1;i<=N;i++)
	{
		k=A[i]/M; //把A中的每個元素按照的範圍值放入對應桶中
		Bucket[k]=new linklist(A[i],Bucket[k]);
	}
	for (k=j=0;k<=100;k++)
	{
		i=j;
		for (p=Bucket[k];p;p=p->next)
			B[++j]=p->value; //把桶中每個元素取出,排序並加入B
		delete Bucket[k];
		qsort(B+i+1,j-i,sizeof(B[0]),cmp);
	}
}
int main()
{
	int *A,*B,N=100,K=10000,i;
	A=new int[N+1];
	B=new int[N+1];
	for (i=1;i<=N;i++)
		A[i]=rand()%K+1; //生成1..K的隨機數
	BucketSort(A,B,N,K);
	for (i=1;i<=N;i++)
		printf("%d ",B[i]);
	return 0;
}

[基數排序]

下面說到我們的重頭戲,基數排序(Radix Sort)。上述的基數排序和桶排序都只是在研究一個關鍵字的排序,現在我們來討論有多個關鍵字的排序問題。

假設我們有一些二元組(a,b),要對它們進行以a爲首要關鍵字,b的次要關鍵字的排序。我們可以先把它們先按照首要關鍵字排序,分成首要關鍵字相同的若干堆。然後,在按照次要關鍵值分別對每一堆進行單獨排序。最後再把這些堆串連到一起,使首要關鍵字較小的一堆排在上面。按這種方式的基數排序稱爲MSD(Most Significant Dight)排序。

第二種方式是從最低有效關鍵字開始排序,稱爲LSD(Least Significant Dight)排序。首先對所有的數據按照次要關鍵字排序,然後對所有的數據按照首要關鍵字排序。要注意的是,使用的排序算法必須是穩定的,否則就會取消前一次排序的結果。由於不需要分堆對每堆單獨排序,LSD方法往往比MSD簡單而開銷小。下文介紹的方法全部是基於LSD的。

通常,基數排序要用到計數排序或者桶排序。使用計數排序時,需要的是Order數組。使用桶排序時,可以用鏈表的方法直接求出排序後的順序。下面是一段用桶排序對二元組基數排序的程序:

/*
 * Problem: Radix Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo: 基數排序 結構數組
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct data
{
	int key[2];
};
struct linklist
{
	linklist *next;
	data value;
	linklist(data v,linklist *n):value(v),next(n){}
	~linklist() {if (next) delete next;}
};
void BucketSort(data *A,int N,int K,int y)
{
	linklist *Bucket[101],*p;//建立桶
	int i,j,k,M;
	M=K/100+1;
	memset(Bucket,0,sizeof(Bucket));
	for (i=1;i<=N;i++)
	{
		k=A[i].key[y]/M; //把A中的每個元素按照的範圍值放入對應桶中
		Bucket[k]=new linklist(A[i],Bucket[k]);
	}
	for (k=j=0;k<=100;k++)
	{
		for (p=Bucket[k];p;p=p->next) j++;
		for (p=Bucket[k],i=1;p;p=p->next,i++)
			A[j-i+1]=p->value; //把桶中每個元素取出
		delete Bucket[k];
	}
}
void RadixSort(data *A,int N,int K)
{
	for (int j=1;j>=0;j--) //從低優先到高優先 LSD
		BucketSort(A,N,K,j);
}
int main()
{
	int N=100,K=1000,i;
	data *A=new data[N+1];
	for (i=1;i<=N;i++)
	{
		A[i].key[0]=rand()%K+1;
		A[i].key[1]=rand()%K+1;
	}
	RadixSort(A,N,K);
	for (i=1;i<=N;i++)
		printf("(%d,%d) ",A[i].key[0],A[i].key[1]);
	printf("\n");
	return 0;
}

基數排序是一種用在老式穿卡機上的算法。一張卡片有80列,每列可在12個位置中的任一處穿孔。排序器可被機械地"程序化"以檢查每一迭卡片中的某一列,再根據穿孔的位置將它們分放12個盒子裏。這樣,操作員就可逐個地把它們收集起來。其中第一個位置穿孔的放在最上面,第二個位置穿孔的其次,等等。

對於一個位數有限的十進制數,我們可以把它看作一個多元組,從高位到低位關鍵字重要程度依次遞減。可以使用基數排序對一些位數有限的十進制數排序

[三種線性排序算法的比較]

從整體上來說,計數排序,桶排序都是非基於比較的排序算法,而其時間複雜度依賴於數據的範圍,桶排序還依賴於空間的開銷和數據的分佈。而基數排序是一種對多元組排序的有效方法,具體實現要用到計數排序或桶排序。

相對於快速排序、堆排序等基於比較的排序算法,計數排序、桶排序和基數排序限制較多,不如快速排序、堆排序等算法靈活性好。但反過來講,這三種線性排序算法之所以能夠達到線性時間,是因爲充分利用了待排序數據的特性,如果生硬得使用快速排序、堆排序等算法,就相當於浪費了這些特性,因而達不到更高的效率。

在實際應用中,基數排序可以用於後綴數組的倍增算法,使時間複雜度從O(N*logN*logN)降到O(N*logN)。線性排序算法使用最重要的是,充分利用數據特殊的性質,以達到最佳效果

BYVoid 原創講解,轉載請註明。


上次修改時間 2017-05-22

相關日誌