冒泡排序：

算法重復(fù)走訪要排序的數(shù)列，一次比較兩個元素，如果它們順序錯誤就交換它們的位置，這樣最大的數(shù)就到了最后，重復(fù)操作即可得到有序數(shù)列。

冒泡排序算法運行：

• 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
• 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
• 針對所有的元素重復(fù)以上的步驟，除了最后一個。
• 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

代碼實現(xiàn)：

public static void main(String[] args) { 
        int[] values = { 3, 1, 6, 2, 9, 0, 7, 4, 5, 8 }; 
        bubbleSort(values); 
        System.out.println(Arrays.toString(values)); 
    } 
    public static void bubbleSort(int[] values) { 
        int temp; 
        for (int i = 0; i < values.length; i++) { 
            for (int j = 0; j < values.length - 1 - i; j++) { 
        //減i原因：內(nèi)層循環(huán)，每循環(huán)完一趟就在數(shù)組末產(chǎn)生一個最大數(shù)，即最大數(shù)就不用比較了。 
                if (values[j] > values[j + 1]) { 
                    temp = values[j]; 
                    values[j] = values[j + 1]; 
                    values[j + 1] = temp; 
                } 
            } 
        } 
    } 

但是上述代碼存在不足之處，優(yōu)化如下：

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

基于冒泡排序的以下特點：(幫助理解)

• 整個數(shù)列分成兩部分：前面是無序數(shù)列，后面是有序數(shù)列。
• 初始狀態(tài)下，整個數(shù)列都是無序的，有序數(shù)列是空。
• 每一趟循環(huán)可以讓無序數(shù)列中最大數(shù)排到最后，(也就是說有序數(shù)列的元素個數(shù)增加1)，也就是不用再去顧及有序序列。
• 每一趟循環(huán)都從數(shù)列的第一個元素開始進行比較，依次比較相鄰的兩個元素，比較到無序數(shù)列的末尾即可(而不是數(shù)列的末尾);如果前一個大于后一個，交換。

判斷每一趟是否發(fā)生了數(shù)組元素的交換，如果沒有發(fā)生，則說明此時數(shù)組已經(jīng)有序，無需再進行后續(xù)趟數(shù)的比較了。此時可以中止比較。

public static void bubbleSort(int[] values) { 
       int temp; 
       int i; 
       // 外層循環(huán)：n個元素排序，則至多需要n-1趟循環(huán) 
       for (i = 0; i < values.length - 1; i++) { 
           // 定義一個布爾類型的變量，標記數(shù)組是否已達到有序狀態(tài) 
           boolean flag = true; 
   /*內(nèi)層循環(huán)：每一趟循環(huán)都從數(shù)列的前兩個元素開始進行比較，比較到無序數(shù)組的最后*/ 
           for (int j = 0; j < values.length - 1 - i; j++) { 
               // 如果前一個元素大于后一個元素，則交換兩元素的值； 
               if (values[j] > values[j + 1]) { 
                   temp = values[j]; 
                   values[j] = values[j + 1]; 
                   values[j + 1] = temp; 
                      //本趟發(fā)生了交換，表明該數(shù)組在本趟處于無序狀態(tài)，需要繼續(xù)比較； 
                       即本躺只要發(fā)生了一次交換，就false 
                   flag = false; 
               } 
           } 
          //根據(jù)標記量的值判斷數(shù)組是否有序，如果有序，則退出；無序，則繼續(xù)循環(huán)。 
           if (flag) { 
               break; 
           } 
       } 
   } 

本文授權(quán)轉(zhuǎn)載自公眾號「良許Linux」。良許，世界500強外企Linux開發(fā)工程師，公眾號里分享大量Linux干貨，歡迎關(guān)注!