原理
????假定待排序的序列為5犬庇、4、3臭挽、2、1葬荷,我們最終需要排列為1纽帖、2、3懊直、4、5雕崩,冒泡排序的原理為將序列分為待排序序列和已排序序列融撞,默認(rèn)所有的數(shù)字都在待排序的序列中,后面每1輪排序中尝偎,將最大的數(shù)字挪到最右邊,比如第1輪將5挪到最右邊肤寝,5就加入到了已排序的序列抖僵,第二輪將4挪到最右邊,也就是5的前面裆针,4就加入到了已排序序列里寺晌,以此類推。放到程序里耘婚,一般是通過2次for循環(huán)來實(shí)現(xiàn)陆赋,第1次循環(huán)是從第1個(gè)數(shù)字開始嚷闭,到倒數(shù)第2個(gè)數(shù)字為止赖临,原因是冒泡排序是當(dāng)前元素跟后面的元素進(jìn)行比對,如果循環(huán)到最后一個(gè)元素兢榨,后面就沒有元素了。第2次循環(huán)也是從第1個(gè)數(shù)字開始凌那,跟第1次循環(huán)不同的是第2次循環(huán)不是到倒數(shù)第2個(gè)數(shù)字為止吟逝,而是到倒數(shù)第2個(gè)數(shù)字再減外層循環(huán)的當(dāng)前次數(shù)為止,原因是每次執(zhí)行外層循環(huán)的時(shí)候块攒,已經(jīng)將最大值挪到了最右側(cè),也就是右側(cè)已經(jīng)是最大值的排序序列麦锯,所以在執(zhí)行內(nèi)循環(huán)時(shí)琅绅,只需要循環(huán)到待排序的末尾就行了。
圖解
紅色:代表每一輪冒泡的過程料祠。
藍(lán)色:已排序隊(duì)列澎羞。
無色:待排序隊(duì)列。
WX20190625-180832@2x.png
Java代碼實(shí)現(xiàn)
/**
* 冒泡排序
* @param arr
*/
public static int[] maoPao(int[] arr) {
// 從第1個(gè)元素開始顺呕,倒數(shù)第2個(gè)元素止括饶。
for(int i = 0;i<arr.length-1;i++){
// 第1個(gè)元素開始,倒數(shù)第2個(gè)元素下標(biāo)減當(dāng)前外循環(huán)下標(biāo)止图焰。
for(int j = 0;j<arr.length-1-i;j++){
// 如果當(dāng)前元素的值大于后面元素的,說明要交換僵闯。
if(arr[j] > arr[j+1]){
// 將當(dāng)前位置的值放到臨時(shí)變量里交換。
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {5,4,2,3,1};
int[] resultArray = SortUtils.maoPao(arr);
String result = Arrays.toString(resultArray);
System.out.println(result);
}