小鹿講演演算法之三大排序演演算法：冒泡、插入、選擇

今天分享的是三種排序演演算法，在面試、實際程式設計中經常會碰到和使用到的，我會帶領大家從分析排序演演算法技巧上以及程式碼實現上全面理解這一知識點的掌握。

一、如何分析一個「排序演演算法」

1. 執行效率

① 最好、最壞、平均時間複雜度

在分析演演算法的好壞時，要分別說出最好、最壞、平均時間複雜度的同時，也要說出最好、最壞時間複雜度對應排序的原始資料是什麼樣的。

② 複雜度繫數、常數、低階

時間複雜度反應的是資料規模 n 很大的時候的一個增長趨勢，它表示的時候會忽略繫數、常數、低階 ，小規模資料除外。

③ 比較次數和移動次數

基於比較的排序演演算法，在分析演演算法效率時，我們要考慮到元素的比較和元素的移動。

2. 記憶體消耗

演演算法的記憶體消耗可以透過空間複雜度來衡量，排序演演算法也不例外。我們取用一個名詞叫做「原地排序」，就是指特定空間複雜度是 O(1) 的排序演演算法。

3. 穩定性

如果待排序的序列中存在值相等的元素，經過排序之後，相等元素之間原有的先後順序不變，就叫做「穩定排序」。

二、氣泡排序

1、演演算法思想

每次冒泡對相鄰的兩個元素進行比較，看是否滿足大小關係，不滿足就進行互換，一次冒泡會讓至少一個元素移動到它應該在的位置。有 n 個資料，需要重覆 n 次。

2、演演算法最佳化

當某次冒泡過程已經沒有資料交換時，說明已經達到完全有序，不用再執行後續的冒泡操作。

3、程式碼實現

 1// 氣泡排序，a 表示陣列，n 表示陣列大小
 2public void bubbleSort(int[] a, int n) {
 3  if (n <= 1) return;
 4
 5 for (int i = 0; i  6    // 提前退出冒泡迴圈的標誌位
 7    boolean flag = false;
 8    for (int j = 0; j 1; ++j) {
 9      if (a[j] > a[j+1]) { // 交換
10        int tmp = a[j];
11        a[j] = a[j+1];
12        a[j+1] = tmp;
13        flag = true;  // 表示有資料交換      
14      }
15    }
16    if (!flag) break;  // 沒有資料交換，提前退出
17  }
18}

4、問題思考

①是否為原地排序

冒泡的過程只涉及相鄰資料的交換操作，只需要常量級的臨時空間，所以它的空間複雜度為 O(1)，是一個原地排序演演算法。

②是否為穩定排序

在氣泡排序中，只有交換才可以改變兩個元素的前後順序。為了保證氣泡排序演演算法的穩定性，當有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的資料在排序前後不會改變順序，所以氣泡排序是穩定的排序演演算法。

③最好、最壞以及平均時間複雜度

最好的情況是資料已經排好序，我們只進行一次氣泡排序就可以了，最好時間複雜度為 O(n) 。最壞的情況是，要排序的資料剛好是倒序排列的，我們只進行 n 此冒泡操作，所以最壞的時間複雜度為  O(n²)，平均時間複雜度為  O(n²)。

三、插入排序（Insertion Sort）

1、演演算法思想

我們將元素分為兩個區間，未排序區間和已排序區間。我們要做的就是在未排序區間取出元素與已排序區間元素進行比較插入到適當位置，以此類推，直到未排序區間元素為空為止（順序為從後向前比較）。

2、程式碼實現

 1// 插入排序，a 表示陣列，n 表示陣列大小（從小到大進行排序）
 2public void insertionSort(int[] a, int n) {
 3  //如果陣列大小為 1 直接傳回
 4  if (n <= 1) return;
 5  //否則進行插入排序
 6  for (int i = 1; i  7    int value = a[i];
 8    int j = i - 1;
 9    // 查詢插入的位置
10    for (; j >= 0; --j) {
11      if (a[j] > value) {
12        a[j+1] = a[j];  // 資料移動
13      } else {
14        break;
15      }
16    }
17    a[j+1] = value; // 插入資料
18  }
19}

 1// 選擇排序，a表示陣列，n表示陣列大小
 2  public static void selectionSort(int[] a, int n) {
 3    if (n <= 1) return;
 4    for (int i = 0; i  5      // 查詢最小值
 6      int minIndex = i;
 7      int minValue = a[i];
 8      for (int j = i; j  9        if (a[j] 10          minValue = a[j];
11    for (int i = 0; i 1; ++i) {
12      // 查詢最小值
13      int minIndex = i;
14      for (int j = i + 1; j 15        if (a[j] 16          minIndex = j;
17        }
18      }
19      if (minIndex == i)
20        continue;
21      // 交換
22      int tmp = a[i];
23      a[i] = a[minIndex];
24      a[minIndex] = tmp;
25    }
26  }

 1氣泡排序中資料的交換操作：
 2if (a[j] > a[j+1]) { // 交換
 3   int tmp = a[j];
 4   a[j] = a[j+1];
 5   a[j+1] = tmp;
 6   flag = true;
 7}
 8
 9插入排序中資料的移動操作：
10if (a[j] > value) {
11  a[j+1] = a[j];  // 資料移動
12} else {
13  break;
14}