3つの線形並べ替えアルゴリズムは、並べ替え、バケツ並べ替え、基数並べ替えを行います.

8881 ワード
アルゴリズム
3つの線形並べ替えアルゴリズムは、並べ替え、バケツ並べ替え、基数並べ替えを行います.
［比較に基づいていない並べ替え］
コンピュータ科学では、順序付けは基礎的なアルゴリズム技術であり、多くのアルゴリズムはこれを基礎として、異なる順序付けアルゴリズムは異なる時間オーバーヘッドと空間オーバーヘッドを有する.並べ替えアルゴリズムは非常に多くの種類があります.比較に基づく並べ替えと呼ばれていますので、これらのアルゴリズムはシーケンス中のデータを比較する必要があります.
比較に基づく並べ替えアルゴリズムはO(NlogN)を突破することができない.簡単な証明は以下の通りです.
N個の数はNがありますつの可能な配列、すなわち比較に基づくソートアルゴリズムの判定ツリーはNである!この葉っぱの結点は、比較回数が少なくともlog(N!)=O(NlogN)です.
比較に基づく順序付けではなく、カウント順序、バケツ順序、およびこれに基づいた基数並べ替えでは、O(NlogN)時間の下限を突破することができる.しかし、比較に基づいていない並べ替えアルゴリズムの使用は条件によって制限されており、例えば要素の大きさ制限があり、逆に比較に基づく並べ替えはこのような制限がない(一定の範囲内).しかし、条件制限があるからといって、比較に基づくものではない並べ替えアルゴリズムが無駄になるわけではなく、特定の場合には特殊な性質データがあり、比較に基づくものではない並べ替えアルゴリズムは非常に巧みに解決できる.
本論文では、比較に基づいていない3つの線形の並べ替えアルゴリズムを重点的に紹介する.
[カウント並び替え]
まず、カウント順(Counting Sort)から紹介します.並べ替えられる整数シーケンスAがあると仮定します.要素の最小値は0以下ではなく、最大値はKを超えません.長さKの線形テーブルCを作成して、各値以上の要素の個数を記録します.
アルゴリズムのアイデアは以下の通りです.
シーケンスAをスキャンして、Aの各要素の値を索引として、出現の個数をCに記入します.このときC[i]は、Aの値がiの要素の個数を表してもよい. 
Cに対して最初から積算を開始し、C[i]を統計値に従って結果を出力する. 
リニアテーブルCによって、並べ替え後のデータを簡単に求めることができます.Bを目標とするシーケンスを定義します.Order[i]は順位iの元素で、Aの中の位置を表します.次の方法で統計することができます.
 
/* Problem: Counting Sort 
 * Author: Guo Jiabao 
 * Time: 2009.3.29 16:27 
 * State: Solved 
 * Memo:      
 */ 
#include  
#include  
#include  
#include  
#include  
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:
"); 
		
		for (i=1;i<=N;i++){
			printf("%d ",A[i]); 
		}
		
		CountingSort(A, B, Order, N, K); 
		
		printf("
After CS:
"); 
		
		for (i=1;i<=N;i++){
			printf("%d ",B[i]); 
		}
		
		printf("
Order:
"); 
		
		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 2 2
After CS:
1 2 2 3 5 5 5、6、8、9、10
Order:
4 1 13、9、6、11、12、14、7、5 
明らかに,計数秩序化の時間複雑さはO(N＋K)であり,空間複雑さはO(N＋K)である.Kが大きくない場合には,これは効率的な線形秩序化アルゴリズムである.より重要なのは、順序付けされた同じ値の要素の元の相対位置が変わらない(Orderに表現されている)という安定した並べ替えアルゴリズムであり、これは計数順序付けの重要な性質であり、この性質によって基数秩序化に適用できるということです.
[バレルの並べ替え]
数の並べ替えは、Cを統計したばかりの時、C[i]はAの中の値iの元素の個数を表してもいいです.この時、直接にCをスキャンすれば、並べ替えの結果を求めることができます.確かにそうですが、この方法はカウントアップではなく、ドラム缶の並べ替えです.正確に言えば、ドラム缶の並べ替えの特別な状況です.
この方法でプログラムを簡単に書き出すことができます.カウントアップよりも簡単です.安定したOrderは求められません.
 
 /** 
  * * Problem: Bucket Sort 
  * Author: Guo Jiabao 
  * Time: 2009.3.29 16:32 
  * State: Solved 
  * Memo:         
  * */ 
 
	#include  
	#include  #include  
	#include  #include  
	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
この特別な実装の形態は時間複雑度がO(N＋K)であり,空間複雑度もO(N＋K)であり,同様に各要素がKの範囲内であることが要求される.もっと一般的に、私たちのKが大きいと、O(K)の空間を直接に開けられないとどうですか?
最初にバケットを定義します.バケットは一つのデータ容器で、各バケットは一つの区間の数を格納します.依然として順序付けされた整数シーケンスAがあり、要素の最小値は0以下であり、最大値はKを超えない.M個の桶があると仮定して、i番目のバケット[i]はiK/Mから(i＋1)K/Mまでの数を記憶し、次のようなバケット順序付けの一般的な方法がある.
スキャンシーケンスAは、各要素の値が属する区間に従って、指定されたバケツに入れます(順番に配置します). 
各バケツの要素を並べ替えて、どんな並べ替えアルゴリズムでもいいです.例えば、迅速な並べ替えです. 
各バケツの中の要素を順に集めて、出力シーケンスに並べます. 
このアルゴリズムを簡単に解析し,データが平均分布を期待する場合,各バレルの要素平均個数はN／Mである.各バケット内の要素の順序付けに使用されるアルゴリズムが高速で並べ替えられている場合、順序付け毎の時間複雑度はO(N／Mlog(N／M))である.全体の時間複雑度はO(N)＋O(M)O(N／Mlog(N／M))＝O(N＋Nlog(N／M))＝O(N＋NlogN−NlogM)である.MがNに近いときは,バレル秩序化の時間的複雑さはO(N)と近似的に考えられる.桶が多ければ多いほど、時間効率が高くなりますが、桶が多ければ多いほど、空間が大きくなります.これから分かるように、時間と空間は矛盾した二つの面です.
バケツの中の要素の順序入れと順序取りは必要であり、これによってバケツ並べ替えが安定した並べ替えアルゴリズムであることが確認され、基数並べ替えに協力することができます.
/* 
 * * Problem: Bucket Sort 
 * * Author: Guo Jiabao 
 * * Time: 2009.3.29 16:50 
 * * State: Solved 
 * * Memo:         
 * */ 

#include  
#include 
#include  
#include  
#include  
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).上記の基数並べ替えとバレル順序はいずれも一つのキーワードの並べ替えを研究しているだけで、複数のキーワードがある並べ替え問題について議論します.
いくつかの2つのタプル(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  
#include 
#include  
#include 
#include  
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("
"); 
						return 0; } 
		}
	}
ベースの順序付けは、旧式のカード着用機に使用されるアルゴリズムである.一枚のカードは80列で、各列は12の位置のいずれかに穴をあけることができます.シーケンサは機械的に「プログラム化」されて、各セットのカードの中のいずれかの列を確認し、穴の開いた位置によってそれらを12つの箱に分けて置くことができます.そうすると、オペレーターは一つ一つそれらを集めることができます.その中で、一番目の位置に穴が開いているのは一番上に置いて、二つ目の位置に穴が開いている二番目などです.
桁数が限られている十進数については、多元的なグループと見なし、上位から下位のキーワードまで重要度を順次減少させることができます.いくつかの桁数の限られた十進数に対しては基数並べ替えが使用されます.
［3つの線形並べ替えアルゴリズムの比較］
全体としては、カウント順序、バケット順序は、比較に基づく順序付けアルゴリズムではなく、その時間複雑さはデータの範囲に依存し、バケット順序は、空間的なオーバーヘッドおよびデータの分布にも依存する.基数の順序付けは、多元的なグループの順序付けに有効な方法であり、具体的には、カウント順序またはバケツの順序付けを使用することを実現する.
迅速な並べ替え、積み上げ順序などの比較に基づく並べ替えアルゴリズムに対して、カウント順序、バケツの並べ替え、基数の並べ替え制限がより多く、高速な並べ替え、積み上げ順序などのアルゴリズムの柔軟性がより良い.しかし、逆に言えば、この3つの線形並べ替えアルゴリズムは線形時間に達することができたのは、順序付けデータの特性を十分に利用しているからであり、高速並べ替え、積み上げ順序付けなどのアルゴリズムを使用すれば、これらの特性を無駄にしたことに相当し、より高い効率には達しない.
実際の応用では、基数秩序化は、O(N logN logN)からO(N＊logN)に時間の複雑さを低下させるために、サフィックス配列の倍加アルゴリズムに使用できる.線形並べ替えアルゴリズムは最も重要なことは,最適効果を達成するために,データの特殊な特性を十分に利用することである.
一方向ハッシュアルゴリズム(Hash)--MD 5アルゴリズム
直接挿入アルゴリズム