排序算法圖解之Java冒泡排序及優(yōu)化

第排序算法圖解之Java冒泡排序及優(yōu)化目錄1.冒泡排序簡介2.圖解算法3.冒泡排序代碼實(shí)現(xiàn)4.冒泡排序算法的優(yōu)化

1.冒泡排序簡介

冒泡排序（BubbleSorting）即：通過對待排序的序列從前往后，依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換位置，使較大的元素逐漸移動到后部，就像水底的氣泡一樣逐漸從水面冒出來，這就是冒泡名稱的由來

2.圖解算法

以將序列{3,9,-1,10,-20}從小到大排序?yàn)槔?/p>

基本思想就是，在每一趟排序?qū)崿F(xiàn)將最大的數(shù)移到序列的最后端！這主要通過比較相鄰兩個元素實(shí)現(xiàn)，當(dāng)相鄰的兩個元素逆序的時(shí)候，我們就交換它們。

第1趟排序：

第1趟排序共比較了4次，將最大的數(shù)10冒泡到了序列的尾部。

第2趟排序：

由于第一趟排序已經(jīng)將最大是數(shù)10給冒泡到了最末端，因此在本次排序中，不需要再比較最后一個元素，故共比較了3次，將子序列（前四個元素）中最大的數(shù)9（整個序列中倒數(shù)第二大的數(shù)）冒泡到了子序列的尾端（原序列的倒數(shù)第二個位置）。

第3趟排序：

在第三趟排序時(shí)，同理，倒數(shù)兩個元素位置已經(jīng)確定，即第一、第二大的數(shù)已經(jīng)排好位置，只需要再將倒數(shù)第三大的數(shù)確認(rèn)即可。故比較2次，實(shí)現(xiàn)倒數(shù)第三大的數(shù)3的位置確定。

第4趟排序：

在第四趟排序時(shí)，只有第一、第二個元素的位置還不確定，只需要比較一次，若逆序，則交換即可。到此，排序算法完成，原序列已經(jīng)排序成為一個遞增的序列！

小結(jié)

一共進(jìn)行了數(shù)組大小-1次趟排序，即外層循環(huán)arr.length-1次；每趟排序進(jìn)行了逐趟減小次數(shù)的比較，即內(nèi)層循環(huán)arr.length-i-1次，i從0依次增加。

3.冒泡排序代碼實(shí)現(xiàn)

參考代碼如下，為了便于觀察結(jié)果，在循環(huán)中添加了相應(yīng)的輸出語句：

importjava.util.Arrays;

*@author興趣使然黃小黃

*@version1.0

*冒泡排序

publicclassBubbleSort{

publicstaticvoidmain(String[]args){

int[]array={3,9,-1,10,-20};

//排序前

System.out.println("排序前:"+Arrays.toString(array));

//冒泡排序

for(inti=0;iarray.length-1;i++){

System.out.println("第"+(i+1)+"趟排序開始!");

for(intj=0;jarray.length-i-1;j++){

//如果前面的數(shù)比后面的數(shù)大，則交換

if(array[j]array[j+1]){

//交換

inttemp=array[j];

array[j]=array[j+1];

array[j+1]=temp;

System.out.println("------第"+(j+1)+"趟排序:"+Arrays.toString(array));

System.out.println("第"+(i+1)+"趟排序完成:"+Arrays.toString(array));

System.out.println("================================================");

//輸出排序后的結(jié)果

System.out.println("排序后:"+Arrays.toString(array));

實(shí)現(xiàn)結(jié)果：

4.冒泡排序算法的優(yōu)化

舉個例子，將待排序的序列改為：{5，1，2，3，4}，用以上算法來處理，觀察一下結(jié)果：

可以發(fā)現(xiàn)，當(dāng)?shù)谝惶伺判蚪Y(jié)束的時(shí)候，序列已經(jīng)排序完成：即將5冒泡到了最后，序列實(shí)現(xiàn)了從小到大排序。但是原冒泡排序算法，還是義無反顧的進(jìn)行了數(shù)組大小-1趟排序（我可真是大冤種?。?/p>

因此，我們需要嘗試對算法進(jìn)行優(yōu)化！

發(fā)現(xiàn)：在冒泡排序的過程中，各個元素都在不斷的接近自己的位置，如果下一趟比較中沒有進(jìn)行過任何交換，則說明序列已經(jīng)有序，則排序算法已經(jīng)可以返回結(jié)果。因此，考慮在排序算法過程中添加一個標(biāo)志flag判斷元素是否進(jìn)行過交換，以減少不必要的冤種行為！

優(yōu)化代碼如下：

importjava.util.Arrays;

*@author興趣使然黃小黃

*@version1.0

*冒泡排序優(yōu)化

publicclassBubbleSort{

publicstaticvoidmain(String[]args){

int[]array={5,1,2,3,4};

//排序前

System.out.println("排序前:"+Arrays.toString(array));

booleanflag=false;//用于標(biāo)記是否進(jìn)行了交換，true則說明進(jìn)行了交換，false表示無

//冒泡排序

for(inti=0;iarray.length-1;i++){

System.out.println("第"+(i+1)+"趟排序開始!");

for(intj=0;jarray.length-i-1;j++){

//如果前面的數(shù)比后面的數(shù)大，則交換

if(array[j]array[j+1]){

//交換

flag=true;//標(biāo)記進(jìn)行了交換

inttemp=array[j];

array[j]=array[j+1];

array[j+1]=temp;

System.out.println("------第"+(j+1)+"趟排序:"+Arrays.toString(array));

System.out.println("第"+(i+1)+"趟排序完成:"+Arrays.toString(array));

System.out.println("================================================");

if(!flag){

//如果沒有進(jìn)行交換則直接退出，說明排序已經(jīng)完成

break;

}else{

//回退

flag=false;