氣泡排序

排序演演算法只氣泡排序

1.時間複雜度。

氣泡排序是一種交換排序，是從陣列中選取第一個數，和其他數位做比較，如果所選取的數位大於其他的數位，就做交換，時間複雜度最好的情況是O(n)，這種就是隻經歷一輪比較就得出準確的結果，最壞的情況是O(n²)，因為執行了兩次for迴圈。先上程式碼吧

public static void main(String[] args) {
        int[] arr = {7, 1, 9, 3, 6};
        int[] arr2 = sort(arr);
        for (int i : arr2) {
            System.out.println(i);
        }
    }
public static void sort(int []arr){
        int tmp = 0;
        for (int i = 0;i < arr.length;i++){
            for (int j = i + 1;j < arr.length;j++){
                
                if (arr[i] > arr[j]){
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

第一層for迴圈用來確定第幾個數位，與其他數位做比較。所以開始是第一個元素7與第二個元素做1比較。

因為arr[i] > arr[j] : arr[0] > arr[1] ：7 > 1，交換7和1.得到上面所示情況。

j++，7和9比較，7 < 9，不做交換。

j++，7和3做比較，7 > 3，交換7和3。

j++，7和5做比較，7 > 5，交換7和5.

此時第一輪結束，i++,自增為1，所以從元素3開始。

經過1輪，i++，此時arr[i] = arr[1] = 3，arr[j] = 9，3 和 9 做比較。3 不大於 9，不進行交換。

j++，3 和 5 做比較，3 不大於 5，不進行交換。

j++，3 和 7 做比較，3 不大於 7，不進行交換。

i++,進行第三輪，首先9 和 5 作比較，9 > 5 ，交換。

j++，9 和 7 做比較，9 > 7 ，交換。

此時陣列有序，排序結束。

穩定性分析

氣泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。如果兩個元素相等，那麼不會進行交換，所以氣泡排序是穩定的排序演演算法。

氣泡排序演演算法改進

氣泡排序是每個數位向後沉，只確定了最大值，可以在每次迴圈之中進行正反兩次冒泡，分別找到最大值和最小值，如此可使排序的輪數減少一半。提升效率，這裡只指出思路，可以嘗試寫下，啦啦啦。