排序之冒泡排序

前言

　　本篇部落格是在伍迷兄的部落格基礎上進行的，其部落格位址點選就可以進去，裡面好部落格很多，我的排序算法都來自于此；一些資料結構方面的概念我就不多闡述了，伍迷兄的部落格中都有詳細講解，而我寫這些部落格隻是記錄自己學習過程，加入了一些自己的了解，同時也希望給别人提供幫助。

　　無論你學習哪種程式設計語言，在學到循環和數組時，通常都會介紹一種排序算法來作為例子，而這個算法一般就是冒泡排序。并不是它的名稱很好聽，而是說這個算法的思路最簡單，最容易了解。是以，哪怕大家可能都已經學過冒泡排序了，我們還是從這個算法開始我們的排序之旅。

基本思想

　 　兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。冒泡的實作在細節上可以很多種變化，我們就最簡單的一種冒泡實作代碼，來講解冒泡排序的思想。

代碼實作

/**
  * 冒泡排序
  * 大的往下沉，小的往上冒
  * @param arr
  */
 public void buttleSort(int[] arr){
     int len = arr.length;
     // i表示第幾輪比較(9個數字的話隻需要比較8次)
     for(int i=1; i<len; i++){
         // 大的往下沉，小的往上冒
         for(int j=len-1; j>=i; j--){
             if(arr[j-1] > arr[j]){        // 若前者大于後者
                 swap(arr,j-1,j);        // 交換arr[j-1]與arr[j]
             }
         }
     }
}      

執行過程模拟

　　假設我們要排序的序列依然是{5,3,7,9,1,6,4,8,2}，當i=1時，變量j由8反向循環到1，逐個比較，将較小值交換前面，直到最後找到最小值放置在了第1的位置。如圖5-1，當i=1，j=8時，我們發 現8>2，是以交換了它們的位置，j=7時，4>2，是以交換……直到j=5時，因為1<2，所在不交換。j=1時，5>1，交 換，最終得到最小值1放置第一的位置。事實上，在不斷循環的過程中，除了将關鍵字1放到第一的位置，我們還将關鍵字2從第九位置提到到了第六的位置。圖中較小的數字如同氣泡般慢慢浮到上面，是以就将此算法命名為冒泡算法。

　　當i=2時，變量j由8反向循環到2，逐個比較，在将關鍵字2交換到第二位置的同時，也将關鍵字4有所提升。

　　後面的過程一樣的，這裡就不在贅述了。

總結

　　冒泡排序是比較好了解的，應該是沒什麼難點，但是上述的代碼是可以改善的。試想一下，如果我們待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是說，除了第一和第二的關鍵字需要交換外，别的都已經是正常的順序。當 i=1時，交換了2和1，此時序列已經有序，但是算法仍然不依不饒的将i=2到9，以及每個循環中的j循環都執行了一遍，盡管并沒有交換資料，但是之後的大量比較還是大大的多餘了。那麼如何進行改善，就當是給大家的思考題了！

　　對改善實在是沒有辦法的，可以點這裡，講到了冒泡排序的優化。