Javaで一般的な7種類のソートアルゴリズムを実現

12775 ワード

java データ構造ソートアルゴリズム

主に以下の一般的なソートとjavaの実装をまとめます.
比較ソート
バブルソート
ソートの挿入
ヒルソート
クイックソート
ヒープのソート
集計ソート
1.比較ソート:0番目からそれぞれ後と比較し、正の順序は交換されず、逆の順序は交換されます.時間複雑度n+(n−1)+.....1=(1+n)n/2=O(n^2).

/**    
 * 2015 10 29   9:53:38
 * @param data
 */
public static void CompareSort(int[] data)
{
	for(int i=0;i<data.length;i++)
	{
		for(int j=i+1;j<data.length;j++)
		{
			if(data[i]>data[j])
			{
				int change=data[i];
				data[i]=data[j];
				data[j]=change;
						
			}
		}
	}
}

2.泡立ちソート:最後にa[n]とa[n-1]を比較し、正の順序は交換せず、逆の順序で交換し、次にa[n-1]とa[n-2]を比較する.遍歴は最小で最上位に並ぶことができ、このようにn遍歴を遍歴すれば、底から上まで、泡立ちのようにソートを実現することができる.時間複雑度O(n^2)

/**
	 *      2015 10 29   9:53:38
	 * 
	 * @param data
	 */
	public static void bubleSort(int[] data) {

		for (int i = 1; i <= data.length; i++) {

			for (int j1 = data.length - 1, j2 = j1 - 1; j2 >= 0; j2--, j1--) {
				if (data[j1] < data[j2]) {
					int change = data[j1];
					data[j1] = data[j2];
					data[j2] = change;
				}
			}
		}

	}

改善:ソートされた部分を削除

/**
	 *      2015 10 29   9:53:38
	 * 
	 * @param data
	 */
	public static void bubleSort(int[] data) {
		for (int i = 0; i <data.length; i++) {
			for (int j1 = data.length - 1, j2 = j1 - 1; j2 >i; j2--, j1--) {				
				if (data[j1] < data[j2]) {
					int change = data[j1];
					data[j1] = data[j2];
					data[j2] = change;
				}
			}
		}

	}

さらに改善:比較できるものがない場合は、ループを終了します.

	/**
	 *      2015 10 29   9:53:38
	 * 
	 * @param data
	 */
	public static void bubleSort(int[] data) {
        Boolean noFinishCompare=true;
		for (int i = 0; i <data.length&&noFinishCompare; i++) {
                noFinishCompare=false;
			for (int j1 = data.length - 1, j2 = j1 - 1; j2 >i; j2--, j1--) {				
				if (data[j1] < data[j2]) {
					int change = data[j1];
					data[j1] = data[j2];
					data[j2] = change;
					noFinishCompare=true;//            
				}
			}
		}

	}

3.ソートの挿入:ソートする配列を2つの部分に分け、一部はソート済み、一部は元で、最初はデフォルトでソートされたのは最初の配列の下付きのみです.次に、2番目の配列からループし、ソートする要素がソートされた部分の位置にあると判断し、挿入します.例えば、2番目の配列が1番目の配列より小さいと判断し、左側に挿入し、それより大きく右側に挿入し、挿入位置を決定する根拠は前の位置より小さく、次の位置より大きくない.時間的複雑度はO(n^2);

/**    
	 * 2015 10 29   11:09:33
	 * @param data
	 */
	public static void inSertSort(int[] data )
	{
		for(int i=1;i<data.length;i++)
		{
			if(data[i]<data[0])
			{
				int change=data[i];//  data[i]		
				
				for(int s=i;s>=1;s--)// 0   i       
				{
					data[s]=data[s-1];
				}
				data[0]=change;// i     
				
				
			}
			if(data[i]>data[0])
			{
				int change=data[i];//  data[i]			
				for(int s=0;s<i;s++ )//         
				{  
					if(change>data[s]&&change<=data[s+1]){//    【i】     【i+1】         
					                                    
					for(int e=i;e>=s+1;e--)
					{
						data[e]=data[e-1];  //         
					}	
					data[s+1]=change;  //  
				}
				}
								
			}
		}
		
	}

改善:前の部分がソートされているため、a[i]の挿入位置を判断するには、前の推定に基づいて判断することができ、a[i-1]>a[i]であれば、a[i-k]

	/**    
	 * 2015 10 29   11:09:33
	 * @param data
	 */
	public static void inSertSort(int[] data )
	{
		for(int i=1;i<data.length;i++)
		{
			int ai=data[i];
			int j;			
			for(j=i-1;j>=0&&data[j]>ai;j--)
			{				
				data[j+1]=data[j];
			}
			data[j+1]=ai;
		}
		
	}

4.ヒルソート:
原理は何ですか:無秩序配列a【1】a【2】a【3】a【4】a【5】a【6】
これをサブシーケンスに分割する:gap=6/2=3;
それぞれ: a【1】a【4】 a【2】a【5】 a【5】a【6】正序不交换,反序交换
サブシーケンスを並べ替えることで、b【1】b【2】b【3】b【4】b【5】b【6】を得る b【1】次にgap=3/2=1である.
それぞれ:b【1】b【2】 b【2】b【3 】 b【3】b【4】 b【4】b【5】 b【5】b【6】
ソート後に得られるシーケンス:c【1】c【2】c【3】c【4】c【5】c【6】
c【1】bと組み合わせると、秩序化シーケンスが得られる.
アルゴリズムコア:いくつかの秩序化されたサブシーケンスに分割され、サブシーケンスをソートし、最後に基本的な秩序化されたシーケンスを得て、挿入ソートを行います.

public static void ShellSort(int[] datas)
	{
		int gap=datas.length/2;
		if(datas.length>0)
		gap=datas.length%2==0?gap-1:gap;
		while(gap>=1)
		{
			for(int i=0;i<=datas.length/2;i++)
			{				
				if(datas[i]>datas[i+gap])
				{
					int exchange=datas[i+gap];
					datas[i+gap]=datas[i];
					datas[i]=exchange;
				}
			}
			gap=gap/2;
		}
		inSertSort(datas);
	}
}

ヒルソートは、最終的には挿入ソートにも使用されます.目的は、挿入ソートの演算を最小限に抑え、許容回数を決定するために変数を定義することです.

/**    
	 * 2015 10 29   11:09:33
	 * @param data
	 */
	public static void inSertSort(int[] data )
	{		
		for(int i=1;i<data.length;i++)
		{
			
			int ai=data[i];
			int j;			
			for(j=i-1;j>=0&&data[j]>ai;j--)
			{	System.out.println("-----num"+num++);		
				data[j+1]=data[j];
			}
			data[j+1]=ai;
		}
		
	}
	
	public static void ShellSort(int[] datas)
	{
		int gap=datas.length/3;
		if(datas.length>0)
		gap=datas.length%2==0?gap-1:gap;
		while(gap>=1)
		{
			for(int i=0;i<=datas.length/2;i++)
			{				
				if(datas[i]>datas[i+gap])
				{System.out.println("-----num"+num++);
					int exchange=datas[i+gap];
					datas[i+gap]=datas[i];
					datas[i]=exchange;
				}
			}
			gap=gap/3;
		}
		inSertSort(datas);
	}

テストデータは次のとおりです.

int[] datas = new int[] {8,15,4,55,98,14,77,35,88,21,546,875,1,65,756,43,4,87,54,11,25,66,78,95,555,423,657,442};

しかし、挿入ソートを呼び出し、印刷されたnum:

-----num125

ヒルソートを使用すると:

-----num65

かつヒルソートのステップ長が異なると演算ツリーも異なります.

public static void ShellSort(int[] datas)
	{
		int gap=datas.length/3;
		if(datas.length>0)
		gap=datas.length%2==0?gap-1:gap;
		while(gap>=1)
		{
			for(int i=0;i<=datas.length/2;i++)
			{				
				if(datas[i]>datas[i+gap])
				{System.out.println("-----num"+num++);
					int exchange=datas[i+gap];
					datas[i+gap]=datas[i];
					datas[i]=exchange;
				}
			}
			gap=gap/2;
		}
		inSertSort(datas);
	}

印刷されたのは次のとおりです.

-----num61

5.クイックソート:
クイックソートは分治法とも呼ばれ、1つの基準数を基準に2つの部分に分けられ、1つはこの数より小さい部分で、1つはこの数より大きい部分で、それからこの2つの部分をこのような法則に従って再帰させます.
2つの秩序に分かれている部分は、
【1】【2】【3】【4】....【k】...【n-1】【n】
まずkey=【1】を基準数としてn下から左へ遍歴し、keyよりも1番目に小さい【k】を取得し、交換位置:【k】【2】【3】【m】......【1】を取得する.【n-1】【n】
それから2から左へ遍歴して、keyより1番目に大きい【m】を見つけて、kの下のマークを交換して2の下のマークで:【k】【2】【3】.【1】.【m】...【n-1】【n】
【1】前の数は【1】よりも小さく、【m】後の数は【m】よりも大きいことがわかります
そしてこの法則に従って、【1】の下から【m】の下まで並べ替えて、左の下まで右の下まで並べ替えて、最終的に2つの部分に分けます....
前のは【1】より小さく、後ろのは【1】より大きい.
次に2つの部分に分けて再帰し、0の下から【1】の前の下、【1】の後の下から【n】の下に表示する.これにより最終的にソートが実現される.

/**    
	 * 2015 10 30   1:50:53
	 * 
	 * @param data
	 */
	public static void FastSortToHalf(int[] data, int leftFirstPosition,int rightLastPosition) {		
		int size = rightLastPosition;
		if (leftFirstPosition < rightLastPosition) {
			while (leftFirstPosition < rightLastPosition) {//          
				int key = data[leftFirstPosition];
				while (rightLastPosition > leftFirstPosition&& data[rightLastPosition] >= key) {
					rightLastPosition--;
				}

				if (leftFirstPosition < rightLastPosition) {
					data[leftFirstPosition] = data[rightLastPosition];
					data[rightLastPosition] = key;
				}

				while (leftFirstPosition < rightLastPosition&& data[leftFirstPosition] <= key) {
					leftFirstPosition++;
				}

				if (leftFirstPosition < rightLastPosition) {
					int changge = data[leftFirstPosition];
					data[leftFirstPosition] = data[rightLastPosition];
					data[rightLastPosition] = changge;
					
					
				}

			}
			FastSortToHalf(data, 0, leftFirstPosition - 1);//          
			FastSortToHalf(data, leftFirstPosition + 1, size);
		}

	}

6.ヒープのソート:
スタックソートが最悪で平均的な場合の時間複雑度はいずれもO(nlongn)であり,比較ソート,バブルソート,挿入ソートよりも性能的に優れている.
思想:最大のスタックを構築し、維持し、最上位の性質を利用してソートを実現する必要があります.
原理:並べ替えられる配列を完全な二叉木と見なし、i番目の位置に対してparentがあればparent位置はi/2、左サブツリーがあれば左サブツリー位置は2*i、右サブツリーがあれば右サブツリー位置は2*i+1、最大スタックを構築する原理は、親ノードがそのサブノードより小さい場合、親ノードとその子ノードの最大ノードを交換し、子ノードはこのようにして、親ノードが子ノードよりも永遠に大きくなるまで、下から上へ再帰し、最終ルートノードが最大数になります.大きなエントリスタックを作成した後、よりノードの値を最後の値と交換し、0-n-1の下付きエントリを大きなエントリスタックを再構築し、このように再帰して最終的にソートします.
したがって、ステップは、1.大きなアイテムスタックを構築する2.ルートノードを最後のアイテムと交換する3.再帰する.

public static void HeapSort(int[] data) {
		
        BuildBiggestHeap(data, data.length);//     
        for(int i=data.length;i>2;i--)//         3   
        {  
        	swap(data, 0,i-1);//         
        	BuildBiggestHeap(data, i);//       
        }

	}

	/**     
	 * 2015 11 2   3:21:02
	 * @param data
	 * @param length
	 */
	public static void BuildBiggestHeap(int[] data,int length) {
		if(length>data.length)
			return;
		for(int i=length/2-1;i>=0;i--){
			int parent_position=i;
			int left_position=i*2+1;
			int right_position=i*2+2;
			
			if(right_position<length)
			{
			
			if(right_position==length-1){//          
				if(data[parent_position]<data[left_position]);
				swap(data, left_position, parent_position);
			}else{//      
				int lagerposition=0;
				lagerposition=data[left_position]>data[right_position]?left_position:right_position;
				lagerposition=data[lagerposition]>data[parent_position]?lagerposition:parent_position;
				if(lagerposition!=parent_position)
					swap(data, parent_position, lagerposition);
			}
			}
		}

	}

	     //  
	    private static void swap(int[] data, int i, int j) {  
	         int tmp=data[i];  
	         data[i]=data[j];  
	         data[j]=tmp;  
	     }

7.集計ソート:
集計ソートは集計操作に確立された有効なソートアルゴリズムであり,このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用である.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの順序テーブルを1つの順序テーブルに結合すると、2ウェイ集計と呼ばれます.
ソート実装の構想は,配列を左右の2つの部分に分け,2つの部分をそれぞれソートし,ソートした2つの部分をマージすることである.
分割の構想は,再帰的に絶えず分割を行い,最終的には長さ2または3のシーケンスに分割することである.
集計の構想は、1つのバッファ配列を構築し、配列長が集計する2つの部分の長さであり、左部分はi、右部分はj、配列下はkであり、a【i】したがって、コード実装のステップは、1.分割である. 2.連結分割を再帰します.

<strong> </strong>private static void MergeSort(int[] data,int firstposition,int mergeiength)
	    {
	    	if(mergeiength==2)
	    	{
	    		sortlength2(data,firstposition);//   2   
	    		return;
	    	}
	    	if(mergeiength==3){
	    		sortlength3(data,firstposition);//   3   
	    		return;
	    	}
            	    	
	    	int mergeleftlength=mergeiength/2;
	    	int mergerightlength=mergeiength-mergeleftlength;
	    	
	    	MergeSort(data, firstposition, mergeleftlength);//        
	    	MergeSort(data, firstposition+mergeleftlength, mergerightlength);//        
	    	
	    	//             
	    	int[] temp=new int[mergeiength];//    ，             
	    	int tempposition=0;	    	
	    	int i=firstposition,j=i+mergeleftlength;
	    	int leftmaxposition=firstposition+mergeleftlength;
	    	int rightmaxposition=firstposition+mergeiength;
	    	while(i<leftmaxposition&&j<rightmaxposition){	    	
	    		if(data[i]>data[j])
	    		 {
	    			temp[tempposition++]=data[j++];
	    			
	    		 }else {
	    			 temp[tempposition++]=data[i++];
	    		 }
	    		
	    	}
	    	 while(tempposition<mergeiength)//       
	    	 {
	    		 if(i<leftmaxposition)
	    		 {
	    			 temp[tempposition++]=data[i++];
	    		 }
	    		 if(j<rightmaxposition){
	    			 temp[tempposition++]=data[j++];
	    		 }
	    	 }
	    		    	
	    	System.arraycopy(temp, 0, data, firstposition, mergeiength);//             
	    }

	    
	    
	    
		private static void sortlength3(int[] data, int firstposition) {
			sortlength2(data, firstposition);//      
			if(data[firstposition+2]<data[firstposition]){
				int s=data[firstposition+2];
				 data[firstposition+2]=data[firstposition+1];
				 data[firstposition+1]=data[firstposition];
				 data[firstposition]=s;
				}
			if(data[firstposition+2]>data[firstposition]&&data[firstposition+2]<data[firstposition+1]){
				int s=data[firstposition+2];
				 data[firstposition+2]=data[firstposition+1];
				 data[firstposition+1]=s;
				}
		}

		private static void sortlength2(int[] data, int firstposition) {
			if(data[firstposition]>data[firstposition+1])
				swap(data, firstposition, firstposition+1);
			
		}

UVA 11478-Halum差分制約

JAva:ダイナミックエージェント