氣泡排序法 Bubble Sort

基本概念:

1. 兩相鄰的元素互相比較(看要做升冪或是降冪)，將元素互換位置，每做完一輪，最後的元素會是最大或最小
2. 下一輪的比較重複以上步驟，除了最後一個元素已經完成排序，不需要再做
3. 持續對越來越少的元素重複步驟，直到沒有任何元素需要比較
4. 可建立一個flag來記錄每一輪的比較是否有執行互換，如果下一輪偵測到上一輪沒有互換則直接完成排序，最優情況時間複雜度可降低到O(n)

最佳時間複雜度: O(n)
最壞時間複雜度: O(n^2)

   static void sort1(int arr[]){
        for(int i=arr.length-1;i>0;i--){
            boolean flag = false;
            for(int j=0;j<i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    flag = true;
                }
            }
            if(!flag) break;
        }
    }

   static void sort2(int arr[]){
        boolean flag;
        int j = arr.length-1;
        do{            
            flag = false;
            for(int i=0;i<j;i++){
                if(arr[i]>arr[i+1]){
                    int tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                    flag = true;
                }
            }
            j--;
        }while(flag);
    }