アルゴリズムノート(6)-バブルソート

バブルソート
アルゴリズムの説明
2つの要素のサイズを比較し、2つの要素の順序が逆の場合、位置を交換すると、各スキャンで最小要素が一番前に配置されます(または、最大要素が一番後ろに配置されます).
 
アルゴリズムステップ
(1)隣接する要素を比較し,第1の要素が第2の要素より大きい場合,それらの順序を交換する.
(2)最初のペアから最後のペアまで手順1を繰り返します.最大の要素が最後の位置に配置されます
(3)すべての要素について上記の手順を繰り返し、最後の位置は操作を必要としないと決定した.
(4)上記の動作は、より小さなシーケンスに対して毎回実行される.
 
アルゴリズム実装Java
 

package algorithm.sort;


/**
 * @author kaichen
 * */
public class Bubble {
	
	public static void sort(int[] arr){
		
		int n = arr.length;
				
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n-i-1; j++){
				if(arr[j] > arr[j+1]){
					swap(arr, j, j+1);
				}
			}
		}
	}
	
	private static void swap(int[] arr, int min, int i) {
		int temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
	}
}

アルゴリズムの時間的複雑さ
最良,最悪,平均時間複雑度はO(n^2)であった.
 
あんていせい
安定したソート