jwt簡介

冒泡排序： （Bubble Sort）是一種簡單的交換排序。之所以叫做冒泡排序，因為我們可以把每個元素當成一個小氣泡，根據氣泡大小，一步一步移動到隊伍的一端，最后形成一定對的順序。

冒泡排序的原理：

我們以一個隊伍站隊為例，教官第一次給隊員排隊是無序的，這時候就需要排隊，按矮到高的順序排列，首先拎出第一第二個比較，如果第一個隊員比第二個要高，則兩個交換位置， 高的放到排到第二個位置，矮的就排到第一個，再把第二個，第三個比較，把高的排到后面一個位置，然后以此類推，直至第一輪所有隊員都比較過一次（記住每次比較都是相鄰的兩個），這樣就可以把最高的排到最后的位置。

總結就是： 每一輪都需要從第一位開始進行相鄰的兩個數的比較，將較大的數放后面，比較完畢之后向后挪一位繼續比較下面兩個相鄰的兩個數大小關系，重復此步驟，直到最后一個還沒歸位的數。

冒泡排序流程圖

我們進行分解看看每一步是怎么執行的

首先我們給個無序數組 [3,14,32,16,53,8] 進行升序排序

• 第一輪：初始值 [3,14,32,16,53,8]

如圖所示，走完第一輪之后，我們得到的結果就是[3,14,16,32,8,53]，此時已經將最大的數53排到了指定位置，所以冒泡排序每一輪只能確定將一個數歸位。即第一趟只能確定將末位上的數歸位， 第二趟只能將倒數第 2 位上的數歸位，依次類推下去

• 第二輪：初始值 [3,14,16,32,8,53]第二輪排序結果[3,14,16,8,32,53]
• 第三輪：初始值 [3,14,16,8,32,53]第三輪排序結果[3,14,8,16,32,53]
• 第四輪：初始值 [3,14,8,16,32,53]第四輪排序結果[3,8,14,16,32,53]
• 第五輪：初始值 [3,8,14,16,32,53]第五輪排序結果[3,8,14,16,32,53] 到這，我們最終排序完成。

Java代碼實現：

public static void bubbleSort(int[] array){
         for(int i=0;i< array.length-1;i++){//控制比較輪次，一共 n-1 趟
             int num = 0; //用來記錄比每輪比較的次數
             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;
                 }
                 //比較一次，加1
                 num =num+1;
 
             }
             //結果輸出
             System.out.print("第"+(i+1)+"輪：[");
             for (int a=0;a< array.length; a++){
                 if(a!=array.length-1)
                 {
                     System.out.print(array[a]+",");
                 }else{
                     System.out.print(array[a]+"]");
                 }
             }
             System.out.println(",比較了："+num+" 次");
         }
     }

輸出結果

第1輪結果：[3,14,16,32,8,53],每輪比較了：5 次
   第2輪結果：[3,14,16,8,32,53],每輪比較了：5 次
   第3輪結果：[3,14,8,16,32,53],每輪比較了：5 次
   第4輪結果：[3,8,14,16,32,53],每輪比較了：5 次
   第5輪結果：[3,8,14,16,32,53],每輪比較了：5 次

我在每輪比較的時候定義了一個num來記錄比較次數，大家可以看到長度為6的數組比較，比較了5輪，每輪都比較了5次， 但是通過上面拆分的每一輪比較細節可以看出，其實約到后面的比較，有一部分已經是排好了，如果某個數比他的下一個位置還小， 就沒有必要和后面已經排好的數據再做比較，這樣只會增加程序運行壓力。

比如，第四輪，8和14比較，換位之后，16,32,53都已經排好了，14再和16比較，不用換位，那16之后的數據已經在第三輪排好，就沒必要再比較16和32,32和53了。

那我們來對程序做一個優化，其實在第一輪把最大的數字排到最后之后，第二輪就不用再和最后一個數字比較，因為最大的數字已經排好，再比較也只能排在最后一位之前了。

優化： 我們就在程序內層循環做一個限制，每輪比較之后，下一輪就比較到array.length-1-i的位置。就是第一輪6位數都比較完成，最大排在最后，第二輪就比較前五個數，把前五個數中最大的排在第五位。這樣以此類推，就可以減少程序中無用的比較。

優化代碼如下:

public static void bubbleSort(int[] array){
         for(int i=0;i< array.length-1;i++){//控制比較輪次，一共 n-1 趟
             int num = 0; //用來記錄比每輪比較的次數
             //每一輪比較一次就排除最后一位，每輪的最后一位一定是這輪最大的，所以-i，
             for(int j=0;j< array.length-1-i;j++){//控制兩個挨著的元素進行比較
                  //換位
                     int temp = array[j];
                     array[j] = array[j+1];
                     array[j+1] = temp;
                 }
                 //比較一次，加1
                 num =num+1;
 
             }
             //結果輸出
             System.out.print("第"+(i+1)+"輪結果：[");
             for (int a=0;a< array.length; a++){
                 if(a!=array.length-1)
                 {
                     System.out.print(array[a]+",");
                 }else{
                     System.out.print(array[a]+"]");
                 }
             }
             System.out.println(",每輪比較了："+num+" 次");
         }
     }

我們再來看看結果：

第1輪結果：[3,14,16,32,8,53],每輪比較了：5 次
第2輪結果：[3,14,16,8,32,53],每輪比較了：4 次
第3輪結果：[3,14,8,16,32,53],每輪比較了：3 次
第4輪結果：[3,8,14,16,32,53],每輪比較了：2 次
第5輪結果：[3,8,14,16,32,53],每輪比較了：1 次

由此，我們可以看到，由之前30次比較減少到15次，所以程序壓力會少很多，程序復雜度也降低了。由上面結果可知：6位長度的數組需要排五輪，每輪次數減1，那如果由n個長度的數組，需要比較多少次呢？

1. 第一輪：6-1
2. 第二輪：6-2
3. 第三輪：6-3
4. 倒數第二輪：2
5. 倒數第一輪：1

得出結果： (n-1)+(n-2)+...+2+1 = n(n-1)/2 =1/2n^2 -1/2n
是一個等差數列，按照時間復雜度規則，直接取最高階項并去除常熟系數等到時間復雜度就是 O(n^2)了

到這，我們的冒泡排序就了解完了。