[アルゴリズム学習]線形時間ソート:カウントソート、ベースソート、バケツソート

アルゴリズム導論では8章で線形時間のソートアルゴリズムを専門にリストし,従来の比較に基づくソートアルゴリズムの上限はO(nlogn)であり,本章では3つのアルゴリズム,カウントソート,基数ソート,バケツソートを紹介した.
最初の接触はカウントソートですleetcodeの上に論文のどんな因子を計算する問題があります.基数ソートとバケツソートは前学期のアルゴリズムの授業で先生が話しました.その時、半分理解して、ずっと彼ら二人が同じアルゴリズムだと思っていました.最近自习してこの1枚を见终わってやっとこの2つのアルゴリズムが全く异なっていることを発见して、いくつかのブログを见ても多くのこの2つのアルゴリズムを混同して、私はこのようによくないと思って、书いたブログは责任を负って、さもなくば初心者を误导しやすくて、私は最初から多くの回り道を歩いて、だからここで自分の理解を総括したいです.
一、カウントソート
1、本のアルゴリズム
カウントソートは、n個の入力要素の各々が0〜k区間の整数であり、kが整数であると仮定する.詳細な原理アルゴリズムの導論は上ではっきり言って、ここで直接私のコードを与えます.

	public static int[] countingSort_extra(int nums[], int k){
		int n=nums.length;
		int[] re=new int[n];
		int[] C=new int[k+1];
		for(int i=0; i<n; i++){
			C[nums[i]]++;
		}
		for(int i=1; i<C.length; i++){
			C[i]+=C[i-1];
		}
		for(int i=n-1; i>=0; i--){//        ，      
			re[C[nums[i]]-1]=nums[i];
			C[nums[i]]--;
		}		
		return re;
	}

本の上で言うのはとてもはっきりしていて、カウントの順序付けは主に2つの特徴があって、1つは比較に基づいていないで、線形の時間の内に完成することができます.また安定したソートは,主に以下に述べる基数ソートの基礎となる.
一つは本の後ろの思考問題で10行目(上のコードの11行)のループを前から後ろに遍歴してもいいかどうかを尋ねることですが、私の理解では、前から後ろに遍歴すればアルゴリズムは正しく動作しますが、ソートの安定性は確保できませんので、基数ソートの基礎として、安定性を確保するために後ろから前に遍歴しなければなりません.
2、空間上の改善
上のメソッド名がcountingSortと呼ばれているのはextraはソート後の配列が別の配列に存在するため、合計2つの追加の配列空間が必要です.改善すれば、ソート後に元の配列に直接書くと、スペースを節約できます.次は私のコードです.
このアルゴリズムは線形時間の並べ替えも実現でき,空間の節約も多いが,同様に不安定であるため,前述したように前後を遍歴するのと同様にカウント並べ替えしか実現できないが,不安定で基数並べ替えには使用できない.

	public static void countingSort(int[] nums, int k){
		int n=nums.length;
		int[] B=new int[k+1];
		int count=0;
		for(int i=0; i<n; i++){
			B[nums[i]]++;
		}
		for(int i=0; i<=k; i++){
			while(B[i]-->0){
				nums[count++]=i;
			}
		}
	}

二、基数ソート
n個のdビット数が与えられ、各ビットにはk個の可能な値がある.radixSortが用いた安定ソート法がO(n+k)を消費する場合,O(d(n+k))時間内にこのような数を並べ替えることができる.
彼はバケツのソートとは全く違い、ここでいくつかの重要なパラメータについて話します.
d:内層ソートの回数を決定するビット数.例えば329は3桁、d=3であり、基数ソートの原理は低から高(必ず低から高に注意)までビット別に比較されるので、アルゴリズム全体は1ビット10ビット100ビットからソートされ、ソートのたびに上のカウントソートが用いられる.
k:可能な取値は、上のカウントソートのkと同じ意味で、可能な取値区間であり、一般的に数字ソートに対する肯定は0-9の10個の取値である.
n:元素の個数、numsである.length.安定したソートを行うため、追加のn長配列を保存する必要があるに違いありません.次の私のコードでは、2つの配列を1つのtemp配列を構築し、2つの配列を1つから別の配列に順次書きます.そうすれば、毎回書く必要はありません.

	private static int[] c;
	//  num   n    
	private static int valInBit(int num, int n){
		int temp=1;
		while(n>0){
			temp*=10;
			n--;
		}
		return num%temp/(temp/10);
	}
	
	//        n       
	private static void countingSort(int[] nums, int[] re, int n){
		Arrays.fill(c, 0);
		for(int i=0; i<nums.length; i++){
			c[valInBit(nums[i], n)]++;
		}
		for(int i=1; i<c.length; i++){
			c[i]+=c[i-1];
		}
		for(int i=nums.length-1; i>=0; i--){
			int val=valInBit(nums[i], n);
			int index=c[val];
			re[index-1]=nums[i];
			c[val]--;
		}
		System.out.println("step"+n+": "+Arrays.toString(re));
	}
	
	/*
	 *   n d  ，       k      
	 */
	public static void radixSort(int[] nums, int d, int k){
		c=new int[k];
		int[] temp=new int[nums.length];
		for(int i=1; i<=d; i++){
			if((i&1)==1){
				countingSort(nums, temp, i);
			}else{
				countingSort(temp, nums, i);
			}
		}	
		
		if((d&1)!=1){
			nums=temp;
		}
		
	} 
	public static void main(String[] args) {
		int[] nums={329,457,657,839,436,720,355};
		radixSort(nums, 3, 10);
		System.out.println(Arrays.toString(nums));
	}

コンソールの出力は次のとおりです.
step1: [720, 355, 436, 457, 657, 329, 839] step2: [720, 329, 436, 839, 355, 457, 657] step3: [329, 355, 436, 457, 657, 720, 839] [720, 329, 436, 839, 355, 457, 657]
三、桶の順序付け
バケツソート[0,1)区間をn個の同じ大きさのサブ区間、またはバケツと呼ぶ.そしてn個の入力数をそれぞれバケツに入れる.出力結果を得るためには、まずバケツごとの数をソートし、バケツごとに巡回し、各バケツの要素を順番に列挙すればよい.
以上はアルゴリズム導論の中の説であり,正直に言うとこの節ではあまり理解していないが,特に後で時間代価がO(n)であることを証明した.
私個人の理解では、バケツのソートの鍵はバケツの区分にあり、ハッシュ関数を設計することに似ていて、各要素が各バケツに分布し、各バケツの要素をソートし、最後に統計します.
以下は本の中の1つの例で、10の要素に対して10つのバケツを分けて、それから第1位の小数で各バケツに対応します.
次は私のコードです.図のチェーンテーブルの代わりにArrayListを使います.

	private static int[] c;
	//  num   n    
	private static int valInBit(int num, int n){
		int temp=1;
		while(n>0){
			temp*=10;
			n--;
		}
		return num%temp/(temp/10);
	}
	
	//        n       
	private static void countingSort(int[] nums, int[] re, int n){
		Arrays.fill(c, 0);
		for(int i=0; i<nums.length; i++){
			c[valInBit(nums[i], n)]++;
		}
		for(int i=1; i<c.length; i++){
			c[i]+=c[i-1];
		}
		for(int i=nums.length-1; i>=0; i--){
			int val=valInBit(nums[i], n);
			int index=c[val];
			re[index-1]=nums[i];
			c[val]--;
		}
		System.out.println("step"+n+": "+Arrays.toString(re));
	}
	
	/*
	 *   n d  ，       k      
	 */
	public static void radixSort(int[] nums, int d, int k){
		c=new int[k];
		int[] temp=new int[nums.length];
		for(int i=1; i<=d; i++){
			if((i&1)==1){
				countingSort(nums, temp, i);
			}else{
				countingSort(temp, nums, i);
			}
		}	
		
		if((d&1)!=1){
			nums=temp;
		}
		
	} 
	public static void main(String[] args) {
		int[] nums={329,457,657,839,436,720,355};
		radixSort(nums, 3, 10);
		System.out.println(Arrays.toString(nums));
	}

コンソール出力は次のとおりです.
[0.12, 0.17]
[0.21, 0.23, 0.26]
[0.39]
[0.68]
[0.72, 0.78]
[0.94]
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
四、まとめ
以上は私が本の上の内容によって自分の理解を结び付けて书いたので、コードはすべて自分でたたいたので、しかも少量のテストを経て、个人のレベルが限られていて完全に间违いがないことを保证することができなくて、主に自分で総括して理解を深めるために使って、间违いがあればみんなが一绪に学习して进歩することを歓迎します.