算法（冒泡排序）

冒泡排序

冒泡排序是我們在做排序時很容易使用到的一種排序方法，簡單的冒泡排序是這樣的

//從大向小進行排序，即從後向前進行排序
    static void SimpleBubbleSort(int arr[]) {
        int temp = 0;
        //外部從0--length-1，内部從0到length-1-i,因為内部的比較是比較arr[j]與arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
           

這樣雖然寫起來簡單，但是會有很多的無效消耗，假設一個數組為[9，2，3，8]，當第一次排序結束後數組已經有序，那麼後面的幾次排序都是無效消耗，那麼我們可不可以檢查數組是否已經有序，如果已經有序就結束排序，這就是下面的寫法

static void bubbleSortOptimize1(int arr[]) {
        int temp = 0;
        boolean flag = false;//用來标記此趟排序是否有位置交換
        //外部從0--length-1，内部從0到length-1-i,因為内部的比較是比較arr[j]與arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }
           

上面的寫法可以判斷數組是否有序，如果有序的話就結束循環。這種寫法僅僅适用與片段有序整體無需的情況，但是對于前面大部分無須，後面小部分有序的情況并沒有顯著提高，對于這種情況我們可以采用記錄最後的交換位置進行優化。即記錄最後的進行位置交換的位置，下一次循環隻循環到記錄的位置就可以結束。寫法如下：

static void bubbleSortOptimize12(int arr[]) {
        int temp = 0;
        boolean flag = false;//用來标記此趟排序是否有位置交換
        int lastPosition = arr.length - 1;
        int tempPos = 0;
        //外部從0--length-1，内部從0到length-1-i,因為内部的比較是比較arr[j]與arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < lastPosition; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                    tempPos = j;
                }
            }
            if (!flag) {
                break;
            }
            lastPosition = tempPos;//如果排序沒有結束将最後交換的位置設給lastPosition
        }
    }
           

上面的寫法已經可以提高很大的效率。還有一種很流行的寫法，雙向冒泡排序。雙向冒泡排序的思想主要就是在一次循環中從前向後排序一次再從後向前排序一次，這樣可以對于類似[0,2,1,3,5,8,9,4]的數組排序更為有利，而且可以相容利于從前排序和利于從後排序的兩種數組，利于從前排序的數組類似[0,2,1,3,4,5]，利于從後排序的數組[0,2,3,4,5,1]。

static void bubbleSortOptimize13(int arr[]) {
        int temp = 0;
        boolean flag = false;//用來标記此趟排序是否有位置交換
        int lastPosition = arr.length - 1;//正向
        int firstPosition = 0;//正向
        int tempPos = 0;
        //外部從0--length-1，内部從0到length-1-i,因為内部的比較是比較arr[j]與arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < lastPosition; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                    tempPos = j;
                }
            }
            lastPosition = tempPos;//如果排序沒有結束将最後交換的位置設給lastPosition
            tempPos = 0;
            if (!flag || firstPosition >= lastPosition) {
                break;
            }
            flag = false;
            for (int j = lastPosition; j > firstPosition; j--) {
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    flag = true;
                    tempPos = j;
                }
            }
            firstPosition = tempPos;
            if (!flag || firstPosition >= lastPosition) {
                break;
            }
        }
    }
           

總結：

在數組特别小的時候，雙向排序并不一定比優化過後的第三種排序效率更高，但是在數組比較大的時候都要比第三種效率更高，這個界限我測着是50,。