數據結構排序 冒泡排序

　　冒泡排序的原理:依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。
　　由於在排序過程中總是小數往前放，大數往後放，相當於氣泡往上升，所以稱作冒泡排序。（百度文庫）

下面是代碼的實現：
   
    測試數組：

    int[] a = { 6, 4, 3, 7, 9, 15, 1, 85, 67, 43 };
    第一種，也是最簡單，同時也是最消耗資源的，代碼如下:
public static int[] sort1Asc(int ap[]) { 
        int k = 0; 
        int b = 0; 
        int ac = 0; 
        for (int i = 0; i < ap.length; i++) { 
            k = 0; 
            for (int j = 0; j < ap.length - 1; j++) { 
                ac++; 
                if (ap[j] > ap[j + 1]) { 
                    b++; 
                    k = ap[j]; 
                    ap[j] = ap[j + 1]; 
                    ap[j + 1] = k; 
                } 
            } 
        } 
        System.out.println("交換次數為：" + b); 
        System.out.println("總共循環次數：" + ac); 
        return ap; 
    } 

執行結果：
              交換次數為：12
              總共循環次數：90
　　第二種，減少總共循環次數（數據量大的時候很節約性能）。根據冒泡排序的原理，我們可以知道，當外層循環執行完一次的時候，其中一個值的位置可定時固定了，也就是他已經排序號了，所以在以後的排序中，我們就不需要訪問他了，這樣就可以減少一半的循環次數，我們知道，主要的排序效果是由內層循環做的，所以目標就是減少二次循環次數，下面是具體代碼：
public static int[] sortAsc(int ap[]) { 
        int k = 0; 
        int b = 0; 
        int ac = 0; 
        for (int i = 0; i < ap.length; i++) { 
            k = 0; 
            //重點，控制二次循環的次數，因為最後i為，已經排好序了，所以就不需要再訪問了 
            for (int j = 0; j < ap.length - i - 1; j++) { 
                ac++; 
                if (ap[j] > ap[j + 1]) { 
                    b++; 
                    k = ap[j]; 
                    ap[j] = ap[j + 1]; 
                    ap[j + 1] = k; 
                } 
            } 
        } 
        System.out.println("交換次數為：" + b); 
        System.out.println("總共循環次數：" + ac); 
        return ap; 
    } 

測試結果：

         交換次數為：12
         總共循環次數：45
  正如你看到的，交換次數沒有改變，但是總共循環次數減少一半。下面我們繼續研究

　　第三種 減少總共循環次數的基礎上，再減少交換次數，我們同新建一個變量，把每次的最小或者最大的位置保存下來，然後等內層循環執行結束，後在進行交換，這種方法主要是指定外層循環的位置為我們的參考值，內層循環的所有比較都是和他進行比較的。當內層循環結束後，如果需要交換，我們才進行交換。下面看代碼：
public static int[] sort2Asc(int ap[]) { 
    int k = 0; 
    int b = 0; 
    int ac = 0; 
    int c = 0; 
    for (int i = 0; i < ap.length; i++) { 
        k = i; 
        for ([color=red]int j =i+1[/color]; j < ap.length ; j++) { 
            ac++; 
            if (ap[k] > ap[j]) { 
                 
                k= j; 
            } 
             
        } 
        if(k!=i) 
        { 
            b++; 
            c = ap[k]; 
            ap[k] = ap[i]; 
            ap[i] = c; 
        } 
    } 
    System.out.println("交換次數為：" + b); 
    System.out.println("總共循環次數：" + ac); 
    return ap; 
} 

測試結果：
   交換次數為：6
   總共循環次數：45
正如你想到的，交換次數減少了很多，而且總共循環次數也改變了。