《戀上資料結構與算法》排序（一）：冒泡排序

一、經典十大排序算法

冒泡排序（Bubble Sort）

• 冒泡排序（Bubble Sort）的基本思想是：通過對待排序數組從頭到尾周遊（從索引較小的元素開始）,依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從數組頭部移向尾部，就象水底下的氣泡一樣逐漸向上冒。

1、算法步驟

• 從頭開始比較每一對相鄰元素

  ，如果第一個比第二個大，就交換它們的位置。
• 執行完一輪後，最末尾那個元素就是最大元素。
• 忽略上一步中曾經找到的最大元素，重複執行步驟一，直到全部元素有序。

2、代碼實作

public static void bubbleSort1(Integer[] array) {
    // 這裡end > 0為終止條件, 隻有end>0,也就是說,end為1的時候,它還可以和它前面的進行比較.
    // end為0的時候, 它前面就沒有元素了
    for (int end = array.length - 1; end > 0; end--) {		// 一共比較多少趟
        for (int begin = 1; begin <= end; begin++) {		// 每一趟中的最大元素
            if (array[begin - 1] > array[begin]) {
                int temp = array[begin - 1];
                array[begin - 1] = array[begin];
                array[begin] = temp;
            }
        }
    }
}
           

• 關于end的範圍

  

3、代碼優化

1、 第一種優化

• 如果

  序列已經完全有序

  ，可以

  提前終止冒泡排序。

  

• 增加一個

  boolean

  值，

  用于判斷每一次循環後

  是否有

  資料交換(交換元素)

  ，如果沒有，則退出排序。說明數組元素是有序的

• 如果資料不是完全有序，此優化會因添加成員變量而導緻計算時間更長。

// 針對下面的方式做優化(當給的數組本來就是有序的,此時就需要優化,不用一一比較了)
public static void bubbleSort2(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        // 這個變量寫在這裡,是為了判斷每一趟排序操作是否将序列變為完全有序.
        // 因為有可能在某一趟之後, 數組的元素就變為完全有序了
        boolean sorted = false; // 是否排過序
        for (int begin = 1; begin <= end; begin++) {
            // 如果不進入下面的判斷,表示本輪循環肯定是有序的
            if (array[begin - 1] > array[begin]) {
                int temp = array[begin - 1];
                array[begin - 1] = array[begin];
                array[begin] = temp;
                sorted = true;  // 排過序
            }
        }
        if (!sorted) break;
    }
}
           

2、 第二種優化

• 如果

  序列尾部

  已經

  局部有序

  ，可以

  記錄最後一次交換的位置，減少比較次數。

• 11元素後面的, 都不比較了

• 記錄

  上一次循環最後一次交換

  的位置，将其

  作為下一次循環的截止位置

  。

public static void bubbleSort3(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        // sortedIndex=1,是針對完全有序的情況: 因為完全有序下,就不會走到下面的if判斷. 是以初始值給1. 最後end=1,一輪掃描就結束了
        int sortedIndex = 1; // 從哪個索引開始,後面的都已經排好序了
        for (int begin = 1; begin <= end; begin++) {
            // 如果不進入下面的判斷,表示本輪循環肯定是有序的
            if (array[begin - 1] > array[begin]) {
                int temp = array[begin - 1];
                array[begin - 1] = array[begin];
                array[begin] = temp;
                // 記錄最後一次交換的位置
                sortedIndex = begin;
            }
        }
        // 将最後一次交換的位置,給end, 作為下次循環的終點
        end = sortedIndex;
    }
}
           

• 平均時間複雜度

  O(n^2)

• 最好時間複雜度

  O(n)

• 空間複雜度

  O(1)

4、排序算法的穩定性（Stability）

• 如果

  相等的2個元素

  ，

  在排序前後的相對位置保持不變

  ，那麼這是

  穩定

  的排序算法。
  • 排序前：

    5，1，3a，4，7，3b

  • 穩定的排序：

    1，3a，3b，4，5，7

  • 不穩定的排序：

    1，3b，3a，4，5，7

• 冒泡排序是

  穩定排序

  算法。

  因為: 冒泡排序過程中,

  兩個相同的元素根本就不會比較

  , 隻有

  左邊的元素 > 右邊的元素

  才會進行交換排序。是以冒泡排序是穩定的排序。

  

5、原地算法（In-place Algorithm）

• 不依賴額外的資源或依賴少數的額外資源，僅依靠輸出來覆寫輸入。
• 空間複雜度為

  O(1)

  的都可以認為是原地算法。
• 非原地算法，稱為

  Not-in-place

  或者

  Out-of-place

  。
• 冒泡排序屬于

  In-place

  。