算法思想01_冒泡排序、插入排序、選擇排序

冒泡排序、插入排序、選擇排序

• 冒泡排序、插入排序、選擇排序
• • Preview_如何分析一個“排序算法”
  • • 排序算法的執行效率
    • 排序算法的記憶體消耗
    • 排序算法的穩定性
  • 冒泡排序（Bubble Sort）
  • • 算法思想
    • 過程優化
    • 算法實作
    • 算法分析
  • 插入排序（Insertion Sort）
  • • 算法思想
    • 算法實作
    • 複雜度分析
  • 選擇排序（Selection Sort）
  • • 算法思想
    • 算法實作
    • 複雜度分析
  • 小結
  • 附加問題

特此聲明：本文的圖檔源自王争老師的《資料結構與算法之美》課程，侵删。

冒泡排序、插入排序、選擇排序

排序算法	時間複雜度	是否基于比較
冒泡、插入、選擇	O(n^2)	是
快速排序、歸并	O(nlogn)	是
桶、計數、基數	O(n)	否

Preview_如何分析一個“排序算法”

排序算法的執行效率

排序算法執行效率的分析，一般從三個方面衡量：

1. 最好情況、最壞情況、平均情況時間複雜度
   • 對于要排序的資料，有的接近有序，有的完全無序。有序度不同的資料，對于排序的執行時間可能會有影響。
2. 時間複雜度的系數、常數 、低階
   • 時間複雜度反映的是資料規模 n 很大的時候的一個增長趨勢，是以它表示的時候會忽略系數、常數、低階。但是實際的軟體開發中，我們排序的可能是 10 個、100 個、1000 個這樣規模很小的資料，是以，在對同一階時間複雜度的排序算法性能對比的時候，我們就要把系數、常數、低階也考慮進來。
3. 比較次數和交換（或移動）次數
   • 基于比較的排序算法的執行過程，會涉及兩種操作，一種是元素比較大小，另一種是元素交換或移動。在分析排序算法的執行效率時，應該把比較次數和交換（或移動）次數也考慮進去。

排序算法的記憶體消耗

算法的記憶體消耗可以通過空間複雜度來衡量。針對排序算法的空間複雜度，引入了一個新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空間複雜度是 O(1) 的排序算法。

冒泡、插入、選擇三種排序算法都是原地排序算法。

排序算法的穩定性

判斷排序算法穩定性的标準：待排序的序列中存在值相等的元素，經過排序之後，相等元素之間原有的先後順序不變。

應用舉例：要給電商交易系統中的“訂單”排序。訂單有兩個屬性，一個是下單時間，另一個是訂單金額。如果我們現在有 10 萬條訂單資料，我們希望按照金額從小到大對訂單資料排序。對于金額相同的訂單，我們希望按照下單時間從早到晚有序。

解決辦法：先按照下單時間給訂單排序。排序完成之後，我們用穩定排序算法，按照訂單金額重新排序。兩遍排序之後，我們得到的訂單資料就是按照金額從小到大排序，金額相同的訂單按照下單時間從早到晚排序的。

冒泡排序（Bubble Sort）

算法思想

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

舉例：4，5，6，3，2，1，從小到大進行排序。

第一趟排序過程如下：

全過程如下：

過程優化

當某次冒泡操作已經沒有資料交換時，說明已經達到完全有序，不用再繼續執行後續的冒泡操作。可以通過一個 boolean 值作為 flag 标記實作。

算法實作

// 冒泡排序，a表示數組，n表示數組大小
	public void bubbleSort(int[] a, int n) {
        if (n <= 1) return;
        
        for (int i = 1; i < n; i++) {
            boolean flag = false;	// 提前退出冒泡循環的标志位
            for (int j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    // 交換
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;	// 表示有資料交換
                }
            }
            if (!flag) break;	// 沒有資料交換，提前退出
        }
    }
           

算法分析

• 空間複雜度：冒泡的過程隻涉及相鄰資料的交換操作，隻需要常量級的臨時空間，是以它的空間複雜度為 O(1)，是一個原地排序算法。
• 是否是穩定的：可以是穩定的。在冒泡排序中，隻有交換才可以改變兩個元素的前後順序。為了保證冒泡排序算法的穩定性，設定交換條件——當有相鄰的兩個元素大小相等的時，不做交換。
• 時間複雜度：
  • 最好的情況下，要排序的資料已經是有序的了，我們隻需進行一次冒泡操作，就可以判斷結束。是以最好情況時間複雜度是 O(n)。
  • 最壞的情況下，要排序的資料剛好是倒序排列的，我們需要進行 n 次冒泡操作，是以最壞情況時間複雜度為 O(n2)。
  • 平均情況（這裡不采用機率論的定量分析），考慮有序度，對于包含 n 個資料的數組進行冒泡排序，最壞情況下，初始狀态的有序度是 0，是以要進行 n(n-1)/2 次交換。最好情況下，初始狀态的有序度是 n(n-1)/2，就不需要進行交換。我們可以取個中間值 n(n-1)/4，來表示初始有序度既不是很高也不是很低的平均情況。

有序度、逆序度、滿有序度

有序度是數組中具有有序關系的元素對的個數。有序元素對用數學表達式表示如下

有序元素對：a[i] <= a[j], 如果i < j。
           

對于一個倒序排列的數組，比如 6，5，4，3，2，1，有序度是 0；對于一個完全有序的數組，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。我們把這種完全有序的數組的有序度叫作滿有序度。

逆序度的定義正好跟有序度相反（預設從小到大為有序）

逆序元素對：a[i] > a[j], 如果i < j。
           

是以三個概念的關系為：逆序度 = 滿有序度 - 有序度

插入排序（Insertion Sort）

算法思想

首先，将數組中的資料分為兩個區間，已排序區間和未排序區間。初始已排序區間隻有一個元素，就是數組的第一個元素。插入算法的核心思想是取未排序區間中的首元素，在已排序區間中找到合适的插入位置将其插入，并保證已排序區間資料一直有序。重複這個過程，直到未排序區間中元素為空，算法結束。

舉例：要排序的資料是 4，5，6，1，3，2，其中左側為已排序區間，右側是未排序區間。

算法實作

// 插入排序，a表示數組，n表示數組大小
	public void insertionSort(int[] a, int n) {
        if (n <= 1) return;
        
        for (int i = 1; i < n; i++) {
            int value = a[i];	// 每一趟要插入到有序部分的資料
            int j = i - 1;
            // 從後向前尋找插入位置
            for (; j>= 0; j--) {
                if (a[j] > value) {
                    a[j + 1] = a[j];	// 大的資料向後移動
                } else {
                    break;	// 此時 a[j] 為插入位置的前驅元素
                }
            }
            a[j + 1] = value;	// 插入資料
        }
    }
           

複雜度分析

• 空間複雜度：O(1)，是原地排序算法。
• 是否是穩定的：可以是穩定的。對于值相同的元素，可以選擇将後面出現的元素，插入到前面出現元素的後面，保證原有的前後順序不變。
• 時間複雜度：
  • 最好情況：O(n)。數組有序，一趟周遊。
  • 最壞情況：O(n2)。數組倒序。
  • 平均情況：O(n2)。數組中插入一個資料的平均時間複雜度取 O(n)，是以整體為O(n2)。

選擇排序（Selection Sort）

算法思想

選擇排序算法的實作思路有點類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素，将其放到已排序區間的末尾。

算法實作

// 将a[]按升序排列
	public static void selectionSort(int[] a, int n) {
        int N = a.length;	// 數組長度
        for (int i = 0; i < N; i++) {
            // 将a[i]和a[i+1...N-1]中最小的元素交換
            int min = i;
            // 找到無序部分最小元素下标
            for (int j = i + 1; j < N; j++) {
                if (a[j] < a[min]) min = j;
            }
            // 交換
            int temp = a[i];
            a[i] = a[min];
            a[min] = a[i];
        }
    }
           

複雜度分析

• 空間複雜度：O(1)，是原地排序算法。
• 是否是穩定的：不穩定。比如 5，8，5，2，9 這樣一組資料，使用選擇排序算法來排序的話，第一次找到最小元素 2，與第一個 5 交換位置，則第一個 5 和中間的 5 順序發生改變。正是是以，相對于冒泡排序和插入排序，選擇排序稍顯遜色。
• 時間複雜度：本算法時間開銷與待排序元素初始狀态無關。
  • 最好情況：O(n2)。
  • 最壞情況：O(n2)。
  • 平均情況：O(n2)。

小結

分析、評價一個排序算法，需要從執行效率、記憶體消耗和穩定性三個方面來看。

本篇涉及的三種排序算法分析結果如下：

排序算法	是否為原地排序	是否穩定	最好 最壞 平均
冒泡排序	是	是	O(n) O(n2) O(n2)
插入排序	是	是	O(n) O(n2) O(n2)
選擇排序	是	否	O(n2) O(n2) O(n2)

這三種時間複雜度為 O(n2) 的排序算法中，冒泡排序、選擇排序，可能純粹停留在理論的層面，學習的目的主要是為了開拓思維，實際開發中應用并不多，但插入排序有一定應用，例如有些程式設計語言中的排序函數的實作原理會用到插入排序算法。對于小規模資料的排序，這三種算法實作代碼非常簡單，用起來比較高效。但是在大規模資料排序的時候，O(n2)的時間複雜度還是偏高。

附加問題

• 為什麼插入排序要比冒泡排序更受歡迎？

答：冒泡排序不管怎麼優化，元素交換的次數是一個固定值，是原始資料的逆序度；同樣的，插入排序不管怎麼優化，元素移動的次數也等于原始資料的逆序度。但是，從代碼實作上來看，冒泡排序的資料交換要比插入排序的資料移動要複雜，冒泡排序需要 3 個指派操作，而插入排序隻需要 1 個。是以從理論上分析，冒泡排序所花費的時間要比插入排序長得多。雖然冒泡排序和插入排序在時間複雜度上是一樣的，都是 O(n2)，但如果希望把性能優化做到極緻，首選插入排序。

// 冒泡排序中資料的交換操作：
if (a[j] > a[j+1]) { // 交換
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

// 插入排序中資料的移動操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 資料移動
} else {
  break;
}
           

插入排序有很大的優化空間，如希爾排序算法。

• 本篇的三種排序算法，都是基于數組實作的。如果資料存儲在連結清單中，這三種排序算法還能工作嗎？如果能，那相應的時間、空間複雜度又是多少呢？

答：隻能改變節點位置，冒泡排序相比于數組實作，比較次數一緻，但交換時操作更複雜；插入排序，比較次數一緻，不需要再有後移操作，找到位置後可以直接插入，但排序完畢後可能需要倒置連結清單；選擇排序比較次數一緻，交換操作同樣比較麻煩。綜上，時間複雜度和空間複雜度并無明顯變化，若追求極緻性能，冒泡排序的時間複雜度系數會變大，插入排序系數會減小，選擇排序無明顯變化。