Java氣泡排序演算法例項分析

排序演算法 Java · 發表 2019-02-18 17:42:33

摘要：對於一些基礎的演算法理解一致不是很透徹。以冒泡演算法為例，Java實現，每次複習後，過段時間總是遺忘，又要重新看，今天索性靜下心來詳細分析一下，雖然是最基礎的演算法，然而小演算法中未必沒有大智慧，供本人及後來人參考。先來看一個最笨的排序： public static void ...

對於一些基礎的演算法理解一致不是很透徹。以冒泡演算法為例，Java實現，每次複習後，過段時間總是遺忘，又要重新看，今天索性靜下心來詳細分析一下，雖然是最基礎的演算法，然而小演算法中未必沒有大智慧，供本人及後來人參考。

先來看一個最笨的排序：

public static void sort1(int[] a){

int count = 0 ;

for(int i=0; i<a.length; i++){

for(int j=0; j<a.length; j++){

count++ ;if(a[i] < a[j]){

int temp = a[i];

a[i] = a[j] ;

a[j] = temp ;

}

System.out.println("#sort1 forloop count - " + count);

}

這是一種比較笨的排序方法，很多新人在寫排序的時候，可能這樣寫理解會比較直觀一些，將陣列迴圈length*length次，所有值倆倆進行一次對比，最後得出結論：

public static void main(String[] args) {

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

sort1(arr);

System.out.println("最終結果：" + Arrays.toString(arr));

}

結果：

#sort1 forloop count - 225

最終結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

可見本次執行225次迴圈；

再來看一個升級版：

public static void sort2(int[] a){

int count = 0 ;

for(int i=0; i<a.length; i++){

for(int j=0; j<a.length-1; j++){

count++ ;

if(a[j] > a[j+1]){

int temp = a[j] ;

a[j] = a[j+1] ;

a[j+1] = temp ;

}

System.out.println("#sort2 forloop count - " + count);

}

本方法對上一個方法進行了進一步的簡化，第一層同樣迴圈length次，而第二層迴圈了length-1次，同時比較只存在於第二層迴圈中，由於第二層的比較重，將當前下標與當前下標+1進行比較，所以總的迴圈數需要length-1，否則會造成陣列越界，這一種演算法比較常見，甚至一些培訓機構對學生進行培訓時也是使用這種排序演算法（至於是老師水平問題還是老師考慮到學生理解能力問題採用本種方法不得而知），本方法對第二層的迴圈進行了-1操作，總排序次數當然要少於第一種。

執行：

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

sort2(arr);

System.out.println("最終結果：" + Arrays.toString(arr));

結果：

#sort2 forloop count - 210

最終結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

本次執行210次迴圈，排序結果同第一種方法，效率有所提升。

對於大學沒有學過演算法和資料結構相關課程，又是初入開發行業的童鞋來說，本種演算法可能需要分析一下才能明白原理。

我們來分析一下第二種方法的缺陷。

先看第二層迴圈：

每次迴圈，都要將第N個數與第N+1個數進行比較，如果第N個數大，則互換位置。例如：

陣列：{12,4,54,3,22,53}

第一次迴圈，j=0，則比較12與4的大小，發現12>4，則互換12與4的位置，結果如下：

{4,12,54,3,22,53}

第二次迴圈，j=1，此次比較12與54的大小，發現12<54，則保持不動，結果如下：

{4,12,54,3,22,53}

第三次迴圈，j=2，比較54和3大小，54>3，則互換，結果如下：

{4,12,3,54,22,53}

第四次迴圈，j=3，比較54和22大小，54>22，互換，結果如下：

{4,12,3,22,54,53}

最後一次迴圈，j=4，比較54和53大小，54>53，互換，結果如下：

{4,12,3,22,53,54}

我們發現，每一次 i 迴圈，都可以將arr[length-1-i]這個位置的數選舉而出，也就是說，整個迴圈只需要length-1次（最後一輪不用排序，因為剩下的最後一個數肯定是最小值），即可完成所有數的排序，所以第二個方法可進行進一步優化：

public static void sort2_up(int[] a){

int count = 0 ;

for(int i=0; i<a.length-1; i++){

for(int j=0; j<a.length-1; j++){

count++ ;

if(a[j] > a[j+1]){

int temp = 0 ;

temp = a[j] ;

a[j] = a[j+1] ;

a[j+1] = temp ;

}

System.out.println("#sort2_up forloop count - " + count);

}

執行：

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

sort2_up(arr);

System.out.println("最終結果：" + Arrays.toString(arr));

結果：

#sort2_up forloop count - 196

最終結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

那麼現在我們來看一下氣泡排序。

以上方法，第一層迴圈length-1次已經沒有問題，那麼來看下第二層迴圈。

每一次我們比較第j個元素和第j+1個元素，但是仔細分析，其實還是有無效比較，我們先把sort2_up中的每一次外層迴圈結果列印一下看看過程：

public static void sort2_up(int[] a){

int count = 0 ;

for(int i=0; i<a.length-1; i++){

for(int j=0; j<a.length-1; j++){

count++ ;

if(a[j] > a[j+1]){

int temp = 0 ;

temp = a[j] ;

a[j] = a[j+1] ;

a[j+1] = temp ;

}

System.out.println("#sort2_up i="+i+", result: " + Arrays.toString(a));

}

System.out.println("#sort2_up forloop count - " + count);

}

#sort2_up i=0, result: [4, 12, 54, 57, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 87]

#sort2_up i=1, result: [4, 12, 54, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 57, 87]

#sort2_up i=2, result: [4, 12, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 54, 57, 87]

#sort2_up i=3, result: [4, 3, 12, 1, 3, 4, 1, 3, 4, 31, 2, 41, 54, 57, 87]

#sort2_up i=4, result: [3, 4, 1, 3, 4, 1, 3, 4, 12, 2, 31, 41, 54, 57, 87]

#sort2_up i=5, result: [3, 1, 3, 4, 1, 3, 4, 4, 2, 12, 31, 41, 54, 57, 87]

#sort2_up i=6, result: [1, 3, 3, 1, 3, 4, 4, 2, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=7, result: [1, 3, 1, 3, 3, 4, 2, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=8, result: [1, 1, 3, 3, 3, 2, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=9, result: [1, 1, 3, 3, 2, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=10, result: [1, 1, 3, 2, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=11, result: [1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=12, result: [1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=13, result: [1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up forloop count - 196

最終結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

那麼我們來看下內層迴圈，也就是j層迴圈：

每一次對第j個元素和第j+1個元素進行比較，迴圈length-1次。

問題出在迴圈length-1次上，為什麼呢，因為從結果我們可以看到，其實每一輪都已經選出了一個最大值，比如第i=0次迴圈，選出了一個最大值，第i=1次迴圈，選出了除上一次最大值之外的最大值，以此類推。

也就是說，j層迴圈中，每次迴圈，後面的比較完全是多餘的，多比較了多少次呢？答案是 i 次。

第一輪迴圈，也就是i=0，此時需要在內層比較所有元素大小，最終選舉出一個最大值；當第二輪迴圈時，i=1，最大值已經選舉出，此時已沒有必要再進行最後一輪j迴圈，j迴圈層只需要執行length-1-i次即可，以此類推。

這就是冒泡迴圈的思想，每一輪迴圈，冒泡選出一個最大值，放到末尾：

public static void bubbleSort(int[] arr) {

int count = 0 ;

System.out.println("待排序陣列：" + Arrays.toString(arr));

for (int i=0;i<arr.length-1;i++) {

for (int j=0;j<arr.length-1-i;j++) {

count++ ;

if (arr[j]>arr[j+1]) {

int temp = arr[j] ;

arr[j] = arr[j+1] ;

arr[j+1] = temp ;

}

System.out.println("第" + (i+1) + "次排序結果：" + Arrays.toString(arr));

}

System.out.println("#bubbleSort forloop count - " + count);

}

執行一下：

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

bubbleSort(arr);

System.out.println("最終結果：" + Arrays.toString(arr));

結果：

待排序陣列：[12, 4, 54, 57, 87, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2]

#第1次排序結果：[4, 12, 54, 57, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 87]

#第2次排序結果：[4, 12, 54, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 57, 87]

#第3次排序結果：[4, 12, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 54, 57, 87]

#第4次排序結果：[4, 3, 12, 1, 3, 4, 1, 3, 4, 31, 2, 41, 54, 57, 87]

#第5次排序結果：[3, 4, 1, 3, 4, 1, 3, 4, 12, 2, 31, 41, 54, 57, 87]

#第6次排序結果：[3, 1, 3, 4, 1, 3, 4, 4, 2, 12, 31, 41, 54, 57, 87]

#第7次排序結果：[1, 3, 3, 1, 3, 4, 4, 2, 4, 12, 31, 41, 54, 57, 87]

#第8次排序結果：[1, 3, 1, 3, 3, 4, 2, 4, 4, 12, 31, 41, 54, 57, 87]

#第9次排序結果：[1, 1, 3, 3, 3, 2, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第10次排序結果：[1, 1, 3, 3, 2, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第11次排序結果：[1, 1, 3, 2, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第12次排序結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第13次排序結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第14次排序結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#bubbleSort forloop count - 105

最終結果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

氣泡排序的思想，說直白點就是每次冒泡選出最大值，並且每次選出的最大值不參與下次排序。

氣泡排序的進一步優化：

上面的氣泡排序演算法確實已經很高效了，但是我們仔細看輸出結果，第12次、13次、14次，其排序結果相同，也就是說，實際到第12次排序已經完成，13、14次為無效操作。我們加個標記，對過程進行進一步優化：

public static void bubbleSort_up(int[] arr) {

int count = 0 ;

System.out.println("待排序陣列：" + Arrays.toString(arr));

for (int i=0;i<arr.length-1;i++) {

boolean isComplete = true ;

for (int j=0;j<arr.length-1-i;j++) {

count++ ;

if (arr[j]>arr[j+1]) {

int temp = arr[j] ;

arr[j] = arr[j+1] ;

arr[j+1] = temp ;

if (isComplete)

isComplete = false ;

}

System.out.println("#第" + (i+1) + "次排序結果：" + Arrays.toString(arr));

if (isComplete)

break;

}

System.out.println("#bubbleSort_up forloop count - " + count);

}

我們每一次外層迴圈開始時，記錄一個完成排序標記，如果內層迴圈有變動，則標記為false，否則為true，看結果：