Java實現冒泡排序算法

• 基本思想

  1. 設數組長度為N。
  2. 比較前後兩個數據，如果前面的數據大於後面的數據，就將兩個數據交換。
  3. 這樣對數組的第0個數據到N - 1個數據進行遍歷後，最大的一個數據就沉到了數組的第N - 1個位置。
  4. N = N - 1,如果N不為0就重復前面兩步，否則排序完成。

• 第一種實現方法

    public void sort(int[] array) {
        int tmp;
        int n = array.length;

        for (int i = 0; i < n; i++) { // 進行n - 1次循環
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

1. 第二種實現方法

   對第一種方法進行優化，設置一個標識，如果這一次發生了交換，則為true，否則為false。明顯如果下一次沒有發生變化，說明排序已經完成。

    public void sort(int[] array) {
        int tmp;
        int n = array.length;

        boolean flag = true;

        while (flag) {
            flag = false;

            for (int j = 1; j < n; j++) {
                if (array[j - 1] > array[j]) {
                    tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                    flag = true;    // 關鍵點
                }
            }
        }
    }

1. 第三種實現方法

   再進一步優化。如果有100個數，只有前面10個無序，那麼在第一次遍歷後，最後發生交換的位置肯定小於10，且這個位置後的數據肯定是有序的，記錄下這個位置，第二次只要從數組頭遍歷到這個位置就可以了。

    public void sort(int[] array) {
        int tmp;
        int flag = array.length;

        while (flag > 0) {
            int k = flag;
            flag = 0;

            for (int j = 1; j < k; j++) {
                if (array[j - 1] > array[j]) {
                    tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                    flag = j; // 關鍵點
                }
            }
        }
    }