再帰適用の集計ソート

アルゴリズム分析集計ソートは集計操作に確立された有効なソートアルゴリズムである.このアルゴリズムは分治法を採用している.(Divide and Conquer)の非常に典型的な応用.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの秩序化テーブルを1つの秩序化テーブルに結合すると、2パス集計と呼ばれる.基本構想:先に再帰的に配列を2つのサブ配列に分割し、数まで再帰するグループには1つの要素しかありません.それから関数を呼び出して2つのサブ配列を並べます.この関数は配列を再帰的に分割するときにスタックに押し込まれるので、この関数の本当の役割は2つの秩序のあるサブ配列をソートすることです.基本手順:1、判断パラメータの有効性、すなわち再帰的な出口;2、まず何もせずに、配列を直接二つのサブ配列に分けます.3、分割配列関数を再帰的に呼び出し、最後に配列に分割された要素は1つしかない.これは配列が秩序化されていることを意味する.4、それからソート関数を呼び出して、2つの秩序ある配列を1つの秩序ある配列に結合する.
5、関数をソートするには、2つの配列の要素を比較し、大きな/小さい要素を一時配列に格納し、1つの配列の要素が光を奪われた場合は、別の配列の要素を直接一時配列に配置し、一時配列の要素を実際の配列にコピーします.
サンプルコード:

public class GuibingSort {
	//first       ，mid       ，last      ，temp[]    
	// mid   ， a      ，        
	//         。      ，              ，
	//      ，               。       ，
	//         ，                  。
	void mergearray(int a[], int first, int mid, int last, int temp[])
	{//         
		int i = first,m = mid;//        
		int j = mid + 1,n = last;//        
		int k = 0;//temp     
		
		while (i <= m && j <= n)//          
		{
			if (a[i] <= a[j])//       temp   
				temp[k++] = a[i++];//       ，  k，i  1
			//  ，  j     ，            j ，  else  
			else
				temp[k++] = a[j++];//j  ，i   
		}
		
		while (i <= m)//         ，     temp    
			temp[k++] = a[i++];
		
		while (j <= n)
			temp[k++] = a[j++];
		
		for (i = 0; i < k; i++)//           a
			a[first + i] = temp[i];
	}
	void mergesort(int a[], int first, int last, int temp[])
	//a[]        ，first, last     
	{
		if (first < last)//           ，first==last，    
		{
			int mid = (first + last) / 2;
			mergesort(a, first, mid, temp);    //    ，        
			mergesort(a, mid + 1, last, temp); //    ，        
			mergearray(a, first, mid, last, temp); //          
		}
	}
	public void sort(int[] a) {
		int n=a.length;
		int[] b=new int[n];
		mergesort(a, 0, n-1, b);
	}
public static void main(String[] args) {
	int[] a= {10,9,8,7,6,5,4,3};
	GuibingSort guibingSort=new GuibingSort();
	guibingSort.sort(a);
	for (int i : a) {
		System.out.println(i);
	}
}
}

実行プロセスの説明:
1回目の集計10と9,ソート結果9,10
2回目の集計8と7,ソート結果7,8
3回目の集計9,10および7,8,並べ替え結果7,8,9,10
6,5,4,3の並べ替え過程は上記と同様であり,並べ替え結果は3,4,5,6であった.
最後に2つの大部分を統合し,最終的な結果を得た.