内部ソート(続き...)

[list]
[*][size=medium][b]挿入ソート[/b][/size]
直接挿入ソート折半挿入ソート2ウェイ挿入ソートテーブル挿入ソートヒルソート
[*][size=medium][b]交換ソート[/b][/size]
バブルソートクイックソート
[*][size=medium][b]選択ソート[/b][/size]
単純選択ソート・スタック・ソート
[*][size=medium][b]集計ソート[/b][size]
2-経路集計ソート
[*][size=medium][b]基数ソート[/b][size]
[/list]
[size=x-large][color=blue]1挿入ソート[/color][/size]
[size=medium][color=blue]1.1直接挿入ソート[/color][size]
2番目の要素から、i番目の要素を前のi-1個の秩序ある要素に挿入します.i-1位置から挿入位置を探し、挿入位置を探しながら要素を後ろに移動します.

/**
	 *       ：
	 *   i         i-1    
	 */
	public static void insertSort(int src[]){
		int len=src.length,j=0;
		int guard=0;
		for(int i=1;i			guard=src[i];
			for(j=i-1;j>=0 && src[j]>guard;j--){//  src[0]       ，        ，        
				//              
				src[j+1]=src[j];//  
			}
			src[j+1]=guard;//         
		}
	}

[size=medium][color=blue]1.2折半挿入ソート[/color][/size]
直接挿入ソートに基づいて二分検索で挿入位置を探し、比較回数を減らし、要素を移動する回数を同じにします.

/**
	 *       
	 *                    
	 *      src[i]           ，
	 *            
	 * @param src
	 */
	public static void bInsetSort(int src[]){
		int len=src.length,j=0;
		int low=0,high=0,mid=0;//       
		int guard=0;//  src[i]
		for(int i=1;i			guard=src[i];
			low=0;high=i-1;
			//1	 src[low…high]            
			while(low<=high){
				mid=(low+high)/2;
				if(src[mid]>=guard){//       
					high=mid-1;
				}else{//       
					low=mid+1;
				}
			}
			//while           (guard    low~high   )：
			//1	low==high， src[mid]>=guard，         high+2  ，high+1      
			// src[mid]			//2	high=low+1,        low==high   ， high=low+j(j>=2)          
			//2	    
			for(j=i-1;j>=high+1;j--){//       
				src[j+1]=src[j];
			}
			src[high+1]=guard;
		}
	}

[size=medium][color=blue]1.3 2ウェイ挿入ソート[/color][/size]
新しい配列を使用します.int src[] = {49,38,65,97,76,13,27,[u]49[/u]}
最初のステップ
[table]
|final|||||||first
|49|*|*|*|*|*|*|*|38
[/table]
ステップ2
[table]
||final||||||first
|49|65|*|*|*|*|*|38
[/table]
ステップ3
[table]
|||final|||||first
|49|65|97|*|*|*|*|38
[/table]
ステップ4
[table]
||||final||||first
|49|65|76|97|*|*|*|38
[/table]
ステップ5
[table]
||||final|||first|
|49|65|76|97|*|*|13|38
[/table]
ステップ6
[table]
||||final||first||
|49|65|76|97|*|13|27|38
[/table]
ステップ7
[table]
|||||final|first||
|49|[u]49[/u]|65|76|97|13|27|38
[/table]
[size=medium][color=blue]1.4テーブル挿入ソート[/color][/size]
静的チェーンテーブルのストレージ構造を使用します.
[size=medium][color=blue]1.5ヒルソート[/color][/size]
[img]http://dl.iteye.com/upload/attachment/483160/e01173c0-3f84-30d1-84c4-2bd61858e7b8.jpg[/img]

/**
	 *     
	 *      dlta[0…t-1]          
	 *      ，        1，     
	 *   
	 * @param src
	 */
	public static void shellSort(int src[],int dlta[]){
		int t=dlta.length;
		//   dlta[0…t-1]    src     
		for(int k=0;k			shellInsert(src,dlta[k]);
		}
	}
	private static void shellInsert(int src[],int dk){
		int len=src.length;
		int third,j;
		//   src       ，         ，    dk
		for(int i=dk;i			third=src[i];
			for(j=i-dk;j>=0 && src[j]>third;j-=dk){
				src[j+dk]=src[j];	//    
			}
			src[j+dk]=third;	//       
		}
	}

[size=x-large][color=blue]2交換ソート[/color][/size]
[size=medium][color=blue]2.1バブルソート[/color][/size]

/**
	 *     
	 *              ，               
	 * 
	 *       ：                          
	 */
	public static void bubbleSort(int src[]){
		int len=src.length;
		int third=0;
		boolean flag=false;
		for(int i=len-1;i>0;i--){//  src[i]     
			flag=false;
			for(int j=0;j				if(src[j]>src[j+1]){
					//    
					third=src[j+1];
					src[j+1]=src[j];
					src[j]=third;

					flag=true;
				}
			}
			if(!flag){
				break;
			}
		}
	}

[size=medium][color=blue]2.2クイックソート[/color][/size]
クイックソートは分治思想を用い,ピボット要素でシーケンス全体を2つに分割し,ブロックを分割する際に2つの頭から中間に1回遍歴する.
交換をすばやくソートするには、次の手順に従います.
[img]http://dl.iteye.com/upload/attachment/483168/19b31124-3cd7-3c55-ba19-16edd3ca704c.png[/img]
プロセス全体をすばやくソート:
[img]http://dl.iteye.com/upload/attachment/483171/1a05f471-cfd6-3534-b029-70bbba06ce4b.jpg[/img]

/**
	 *     
	 *       ，             ，          
	 *           
	 * @param src
	 */
	public static void qSort(int src[],int low,int high){
		if(low			int pivotLoc=partition(src,low,high);
			qSort(src,low,pivotLoc-1);//        ，  pivotLoc     
			qSort(src,pivotLoc+1,high);//        
		}
	}
	//            
	//     src[low…high]   ，      ，      ，  
	//    ( )      （ ）  
	private static int partition(int src[],int low,int high){
		int pivot=src[low];//              
		while(low			//          ，     ，   
			while(src[high]>=pivot && low			src[low]=src[high];//               
			while(src[low]<=pivot && low			src[high]=src[low];
		}
		//   low==high     ，  src[low]               ，
		//               。             ， low（ high）
		//              
		src[low]=pivot;
		return low;
	}

[size=x-large][color=blue]3選択ソート[/color][/size]
[size=medium][color=blue]3.1単純選択ソート[/color][/size]
最小の要素とiの位置の要素の交換を選択し、選択中に最小の要素のインデックス値を交換する必要はありません.

/**
	 *       
	 *   n-i           i       （           ）
	 */
	public static void selectSort(int src[]){
		int min=0,len=src.length;
		int third=0;
		for(int i=0;i			min=i;
			for(int j=i+1;j				if(src[j]			}
			//              src[i]
			third=src[min];
			src[min]=src[i];
			src[i]=third;
		}
	}

[size=medium][color=blue]3.2スタックソート[/color][/size]
ヒープ定義:
小天井スタック:k(i)<=k(2 i)&&k(i)<=k(2 i+1)
大頂炉:k(i)>=k(2 i)&&k(i)>=k(2 i+1)
(i=1,2,...,n/2下向きに整列)
1まず無秩序シーケンスをヒープ構造に調整する
2スタックトップ要素と最後の位置iの要素を交換し、0...i-1要素を新しいスタックに調整します.
3スタックトップ要素が最後の要素になるまで2ステップ目を続けます.
[img]http://dl.iteye.com/upload/attachment/483179/3b2e315d-af76-3372-82b6-9e796a503325.png[/img]
[img]http://dl.iteye.com/upload/attachment/483181/da0d76f5-6de8-35a0-a070-e05272d2ecc4.gif[/img]

/**
	 *    
	 * @param src
	 */
	public static void headSort(int src[]){
		int third=0;
		//            ，   src.length/2    
		for(int i=src.length/2-1;i>=0;i--){// src[1…src.length]     
			heapAdjust(src,i,src.length-1);
		}
		for(int i=src.length-1;i>0;i--){//      src[i]  ，  src[0…i-1]        
			third=src[0];
			src[0]=src[i];
			src[i]=third;

			heapAdjust(src,0,i-1);
		}
	}
	//   s           src[s…m]  s          
	private static void heapAdjust(int src[],int s,int m){
		//src[s…m] src[s]         
		//     src[s]   ， src[s…m]
		//       
		int rc=src[s];
		for(int j=2*s+1;j<=m;j=j*2+1){
			if(j				//j				j++;		//j        
			}
			if(rc>=src[j]){break;}//third     s 
			src[s]=src[j];s=j;
		}
		src[s]=rc;	//  
	}

[size=x-large]集計ソート[/size]
[size=medium]2-路帰並び順[/size]
[img]http://dl.iteye.com/upload/attachment/483191/e93445d3-ac59-3693-8ebe-3c4bd245ec01.jpg[/img]

/**
	 * 2-          :
	 *              
	 *                  s==t
	 */
	public static void mergerSort(int src[]){2-12
		mSort(src,0,src.length-1);
	}
	private static void mSort(int src[],int s,int t){
		int m;
		// src[s…t]        
		if(s			m=(s+t)/2;	//  
			mSort(src,s,m);		//         
			mSort(src,m+1,t);
			merge(src,s,m,t);
		}
	}
	private static void merge(int src[],int i,int m,int n){
		//    src[i…m] src[m+1…n]      tr[i…n]
		int tr[]=new int[n+1];
		int k=i,j=m+1,low=i;
		while(i<=m && j<=n){// src         tr
			if(src[i] <= src[j]){tr[k++]=src[i++];}
			else tr[k++]=src[j++];
		}
		//        
		while(j<=n) tr[k++]=src[j++];
		while(i<=m) tr[k++]=src[i++];

		//      
		for(k=low;k <= n;k++){src[k]=tr[k];}
	}

[size=x-large]基数ソート[/size]