泡立ちソートとその最適化アルゴリズム(JAVA/面接常問)

バブルソートと最適化アルゴリズム

原始泡

最適化1

最適化2

最適化3(カクテルソート)

カクテルソート最適化

泡の順番は何が聞きやすいですか?一つ一つ過去に比べて、何か考察しやすいことがあるのではないでしょうか.面接の中で試験官はきっと原始的なアルゴリズムを聞かないで、すべてあなたに改善の最適化をさせて、そんなに泡が出て目立たないが、最適化の構想もとても重要です!
私はネット上で見た資料に基づいて泡の順序と最適化のアルゴリズムを整理して、もし間違いや不足点があれば、皆さんの指摘を歓迎します!!伝言もメールアドレスも私~メールアドレス([email protected])
オリジナルバブル
バブルソートの考え方では、隣接する要素を2つ比較し、サイズに応じて要素の位置コードを交換します.

public int[] bubbleSort(int array[]) {
	int temp = 0;
	for(int i = 0;i<array.length;i++) {
		for(int j = 1;j < array.length;j++) {
			if(array[j-1] > array[j]) {
				temp = array[j];
				array[j] = array[j-1];
				array[j-1] = temp;
			}
		}
	}
	return array;
}

時間的複雑度はO(n^2),空間的複雑度はO(1)である.
最適化1
ある内ループでは既に秩序が整い,外ループはこれ以上行う必要がないので,タグを設定することで余分なループを終了することができる.

public int[] bubbleSort(int[] array) {
		int temp = 0;
		for(int i = 0;i < array.length;i++) {
			boolean isSorted = true;//        true
			for(int j = 1;j < array.length;j++) {
				if(array[j-1] > array[j]) {
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
					isSorted = false;//         
				}
			}
			if(isSorted) {
				break;//           
			}
		}
		return array;
	}

最適化2
この最適化を説明するために、次に例を挙げます:array:5,6,4,2,8,9,10最初の遍歴:5と6が交換しない->5,6,4,2,8,9,10,9,10・・・・・・・・・・・・6と4が交換->5,4,6,2,8,9,10・・・・・・・・6と2が交換->5,4,8,9,4が交換->5,4,4,6,6,4,6,2,6,9,10・・・・・・・・・・・・・・・・・・・・6と8が交換しない->5,4,6,8,8,8,9,10,9,10・・・・・・・・・・・・・・・・・・・・・・8と9は交換しない->5,4,2,6,8,9,10・・・・・9と10は交換しない->5,4,2,6,8,9,10*という数列の特徴は前半が無秩序で後半が秩序であるため秩序領域は交換する必要がなく,秩序領域を定義できれば意味のない比較を免れることができるのであれば,このような状況を回避するにはどうすればよいのでしょうか.各ラウンドのソートの最後に、最後の交換の下付きラベルを記録することができます.その位置は無秩序配列の境界であり、その後は秩序化されています.最適化コードは次のとおりです.

	public int[] bubbleSort(int[] array) {
		int temp = 0;
		//           
		int lastExchangeIndex = 0;
		//           
		int right = array.length-1;
		for(int i = 0;i < array.length;i++) {
			//    ，        true
			boolean isSorted = true;
			for(int j = 1;j < right;j++) {
				if(array[j-1] > array[j]) {
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
					isSorted = false;//         
					lastExchangeIndex = j-1;//               
				}
			}
			right = lastExchangeIndex;
			if(isSorted) {
				break;//           
			}
		}
		return array;
	}

最適化3(カクテルソート)
カクテルのソートは時計の振り子のように、第1ラウンドは左から右、第2ラウンドは右から左...

	public int[] sort(int[] array) {
		int temp = 0;
		
		for(int i = 0;i < array.length/2;i++) {
			//    ，        true
			boolean isSorted = true;
			//   ，      
			for(int j = i;j < array.length-i-1;j++) {
				if(array[j] > array[j+1]) {
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
					isSorted = false;//         
					
				}
			}
			if(isSorted) {
				break;
			}
			isSorted = true;//              true
			//   ，    
			for(int j = array.length-1-i;j>i;j--) {
				if(array[j-1] > array[j]) {
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
					isSorted = false;
				}
			}
			if(isSorted) {
				break;//           
			}
		}
		return array;
	}

これはカクテルの並べ替えの原始的な実現で、1つの大きい循環セットの2つの小さい循環で、1つの循環は左から右まで、2つ目は右から左までです.
カクテルソートの最適化
さらに最適化できますか??最適化2の方法を参照:各ラウンドの秩序領域を定義し、コードは以下の通りである.

	public int[] sort(int[] array) {
		int temp = 0;
		int lastRightExchangeIndex = 0;//        
		int lastLeftExchangeIndex = 0;//        
		int right = array.length-1;//       
		int left = 0;//       
		for(int i = 0;i < array.length/2;i++) {
			//    ，        true
			boolean isSorted = true;
			//   ，      
			for(int j = left;j < right;j++) {
				if(array[j] > array[j+1]) {
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
					isSorted = false;//         
					lastRightExchangeIndex = j;
					
				}
			}
			right = lastRightExchangeIndex;
			if(isSorted) {
				break;
			}
			isSorted = true;//              true
			//   ，    
			for(int j = right;j>left;j--) {
				if(array[j-1] > array[j]) {
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
					isSorted = false;
					lastLeftExchangeIndex = j;
				}
			}
			left = lastLeftExchangeIndex;
			if(isSorted) {
				break;//           
			}
		}
		return array;
	}