Android教程網
  1. 首頁
  2. Android 技術
  3. Android 手機
  4. Android 系統教程
  5. Android 游戲
 Android教程網 >> Android技術 >> Android開發 >> 關於android開發 >> 數據結構排序 冒泡排序

數據結構排序 冒泡排序

編輯:關於android開發

  冒泡排序的原理:依次比較相鄰的兩個數,將小數放在前面,大數放在後面。即在第一趟:首先比較第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
正如你想到的,交換次數減少了很多,而且總共循環次數也改變了。

  1. 上一頁:
  2. 下一頁:
熱門文章
閱讀排行版
Copyright © Android教程網 All Rights Reserved