優化氣泡排序

問題：
給定一個整型陣列, 實現氣泡排序 (升序排序)

一般我們寫出來的是這個程式碼：

public static void bubbleSort(int[] array) {
        for(int i = 0;i < array.length -1;i++) {
            if(array[i] > array[i+1]) {
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {6,8,13,2,9};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

這個程式碼呢，不能說他錯，但是呢大家都會寫，在面試的時候就體現不出來自己的優勢，所以我們需要對這個程式碼進行優化：

1、第一輪的判斷將整個陣列的最大值放在了最後面，第二輪的判斷是將除過第一次選出的最大值以外的剩餘數位中的最大值放在了倒數第二位，我們已經知道從後往前是從大到小的順序已經排好，所以我們沒必要每次都進行最後一個數位和前一個數位的比較，我們可以再加個迴圈，用來減少判斷每次後面已經排好的順序，只進行前面數位的比較排序即可。

第3趟：

第4趟：

2、我們需要判斷陣列是否已經排好序，防止重複比較
分為兩種：一就是給定的陣列本身就是有序的，二就是陣列在排序的過程中就已排好

下面給出我們優化後的程式碼：

public static void bubbleSort(int[] array) {
        for(int i = 0;i < array.length -1;i++) {
            boolean flg = true;//標記
            for (int j = 0; j < array.length-1-i; j++){
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flg = false;
                }
            }
            if(flg == true) {
                break; // 說明給定的陣列是排好序的陣列
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {6,8,13,2,9};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

執行結果：