論排序算法之冒泡排序（升序）

- 排序原理

1. 比較相鄰的元素。如果第一個比第二個，就交換他們兩個；
2. 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數；
3. 循環往複，針對所有的元素重複以上的步驟，除了最後一個；
4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較

- 算法分析

若檔案的初始狀态是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數

和記錄移動次數

均達到最小值：

。

是以，冒泡排序最好的時間複雜度為

若初始檔案是反序的，需要進行 N-1 趟排序。每趟排序要進行 N-i 次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：

冒泡排序的最壞時間複雜度為

- 初級版

public void bubbleSort(int [] nums) {
        int len = nums.length - 1;
        for (int i = 0; i <= len; i++) //外循環為排序趟數，len個數進行len-1趟
            for (int j = 0; j <= len - 1 - i; j++) {//内循環為每趟比較的次數，第i趟比較len-i次
                if (nums[j] > nums[j + 1]) { //逆序則交換
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
    }           

- 進階版

public void bubbleSort2(int [] nums) {
        int len = nums.length - 1;
        for (int i = 0; i <= len; i++) { //外循環為排序趟數，len個數進行len-1趟
            boolean isSwap = false;
            for (int j = 0; j <= len - 1 - i; j++) {//内循環為每趟比較的次數，第i趟比較len-i次
                if (nums[j] > nums[j + 1]) { //逆序則交換
                    isSwap = true; // 如有交換 置為true
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
            if (!isSwap) break; // 如果内層沒有發生任何一次交換，則數組已經有序
        }
    }