資料結構之--冒泡排序

        冒泡排序隻會操作相鄰的兩個資料。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求。如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置，重複 n 次，就完成了 n 個資料的排序工作。

但是正常的冒泡排序還可以優化，當某次冒泡操作已經沒有可交換的資料時，說明已經完全達到有序了，不用再繼續執行後續的冒泡，此時給他一個标簽，當目前資料沒有發生交換時，退出目前操作。

代碼示例：

public static void main(String[] args) {
    MaoPao mp = new MaoPao();
    Random ran = new Random();
    Set<Integer> set = new HashSet<Integer>();
    while(set.size()==100000?false:true){
        int num = ran.nextInt(1000000)+1;
        set.add(num);
    }
    Integer[] a = new Integer[set.size()];
    set.toArray(a);
    long l = System.currentTimeMillis();

    mp.bubbleSort(a,a.length);
    System.out.println("冒泡排序後:"+ Arrays.toString(a));
    
    long l1 = System.currentTimeMillis();
    System.out.println(l1-l);
}

// 冒泡排序，a 表示數組，n 表示數組大小
public void bubbleSort(Integer[] a, int n) {
    if (n <= 1){
        return;
    }

    for (int i = 0; i < n; ++i) {
        // 提前退出冒泡循環的标志位
        boolean flag = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j+1]) { // 交換
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                flag = true;  // 表示有資料交換
            }
        }
        if (!flag){// 沒有資料交換，提前退出
            break;
        }
    }
}
           

冒泡排序過程隻涉及相鄰的資料交換操作，是以他的誰空間複雜度為O(1)，是一個原地排序算法。

而且為了保證冒泡排序的算法穩定性，當有相鄰的兩個元素大小相等時，我們不交換資料，相同大小的資料在排序前後不會改變順序，是以冒泡排序算是穩定排序算大。

冒泡排序最好的情況時間複雜度是O(n)，而最壞的情況是，排序的資料剛好都是倒叙排列的，我們需要進行n西冒泡操作，是以最壞情況時間複雜度為O(n2)。