看動畫學演算法之:排序-冒泡排序
簡介
排序可能是所有的演算法中最最基礎和最最常用的了。排序是一個非常經典的問題，它以一定的順序對一個數組（或一個列表）中的項進行重新排序。
排序演算法有很多種，每個都有其自身的優點和局限性。
今天我們來學習最最簡單的冒泡排序演算法。
冒泡排序的原理
冒泡排序的原理很簡單，我們想像一下一個一個的氣泡上浮的過程。
假設我們有八個數字 29,10,14,37,20,25,44,15 要進行排序。
我們先用一個動畫圖來直觀的觀察一下整個冒泡排序的過程：
排序共進行八輪，每一輪都會做兩兩比較，並將較大的元素右移，就像冒泡一下。
一輪結束之後，八個元素中最大的那個元素44將會移動到最右邊。
然後再重複其他的幾輪。最終得到一個完全排序的數組。
也可以這樣看：
第一輪是將八個元素中的最大值44交換移動到最右位置。
第二輪是將八個元素中的次大值37交換移動到最右位置。
以此類推。
冒泡排序演算法的java實現
我們先看一個最簡單的冒泡演算法：
public class BubbleSort {
public void doBubbleSort(int[] array){
log.info("排序前的數組為:{}",array);
//外層循環,遍歷所有輪數
for(int i=0; i< array.length-1; i++){
//內層循環，兩兩比較，選中較大的數字，進行交換
for(int j=0; j<array.length-1; j++){
if(array[j]>array[j+1]){
//交換兩個數字
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
log.info("第{}輪排序後的數組為:{}", i+1, array);
}
}
public static void main(String[] args) {
int[] array= {29,10,14,37,20,25,44,15};
BubbleSort bubbleSort=new BubbleSort();
bubbleSort.doBubbleSort(array);
}
}
這個演算法就是兩層遍歷，外層遍歷表示的是進行的輪數。內層遍歷表示的是每一輪的排序。
我們看下輸出結果：
冒泡演算法的第一次改進
分析上面的遍歷過程，我們可以發現，第一次排序之後，44已經放到最右邊的位置了，已經排好序了。
第二次排序之後，37也已經排好序了。每過一輪，內部循環需要比較的次數就可以減一。
這就意味著，在內部循環的時候，我們只需要進行array.length-i-1次比較就可以了。
修改程式碼如下：
public class BubbleSort1 {
public void doBubbleSort(int[] array){
log.info("排序前的數組為:{}",array);
//外層循環,遍歷所有輪數
for(int i=0; i< array.length-1; i++){
//內層循環，兩兩比較，選中較大的數字，進行交換, 最後的i個數字已經排完序了，不需要再進行比較
for(int j=0; j<array.length-i-1; j++){
if(array[j]>array[j+1]){
//交換兩個數字
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
log.info("第{}輪排序後的數組為:{}", i+1, array);
}
}
public static void main(String[] args) {
int[] array= {29,10,14,37,20,25,44,15};
BubbleSort1 bubbleSort=new BubbleSort1();
bubbleSort.doBubbleSort(array);
}
}
運行結果：
可以看到運行結果其實沒什麼不同，只不過我們少做了幾次比較。
冒泡演算法的第二次改進
從上面的結果，我們可以看到實際上第5輪排序過後就已經排序完成了。但是我們仍然進行了第6，7次排序。
有沒有什麼辦法可以判斷排序是不是已經完成了呢？
我們考慮一下，在內部循環中，我們是進行兩兩比較，然後交換位置。
如果在某一次遍歷中，沒有進行交互，這就意味著排序已經完成了。
所以我們可以再引入一個flag來做判斷。
public class BubbleSort2 {
public void doBubbleSort(int[] array){
log.info("排序前的數組為:{}",array);
//外層循環,遍歷所有輪數
for(int i=0; i< array.length-1; i++){
//添加一個flag，如果這一輪都沒有排序，說明排序已經結束，可以提前退出
boolean flag=false;
//內層循環，兩兩比較，選中較大的數字，進行交換, 最後的i個數字已經排完序了，不需要再進行比較
for(int j=0; j<array.length-i-1; j++){
if(array[j]>array[j+1]){
//交換兩個數字
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = true;
}
}
log.info("第{}輪排序後的數組為:{}", i+1, array);
if(!flag)
{
log.info("本輪未發生排序變化，排序結束");
return;
}
}
}
public static void main(String[] args) {
int[] array= {29,10,14,37,20,25,44,15};
BubbleSort2 bubbleSort=new BubbleSort2();
bubbleSort.doBubbleSort(array);
}
}
運行結果如下：
從結果我們可以看到少了一輪排序，提升了速度。
冒泡排序的時間複雜度
雖然我們可以在冒泡的時候進行一些性能優化，但是基本上還是要進行嵌套的兩次遍歷。遍歷次數近似的=n*n，所以冒泡排序演算法的時間複雜度是O(n²)。
本文的程式碼地址：
本文已收錄於 //www.flydean.com/algorithm-bubble-sort/
最通俗的解讀，最深刻的乾貨，最簡潔的教程，眾多你不知道的小技巧等你來發現！
歡迎關注我的公眾號:「程式那些事」,懂技術，更懂你！
