插入排序

1. 插入排序演算法
2. 插入排序示例
3. 插入排序演算法的實現
4. 插入排序演算法複雜度

插入排序是一種簡單的基於比較的排序演算法。在這個演算法中，我們維護兩個子陣列：一個已排序子陣列和一個未排序子陣列。未排序子陣列中的一個元素在排序子陣列中找到它的正確位置，並被插入其中。這類似於人們對手中的一副牌進行排序的方式。它被命名為插入排序，因為它的工作原理是在正確的位置插入一個元素。這種演算法對小資料集很有效，但不適合大資料集。

插入排序演算法

假設我們有一個包含 n 個元素的無排序陣列 A[]，第一個元素 A[0] 已經被排序並在排序後的子陣列中。第一個元素 A[0] 已經被排序，並且在排序子陣列中。

插入排序示例

假設我們有陣列：(5,3,4,2,1). 我們將使用插入排序演算法對其進行排序。

• 第一次迭代

鍵：A[1]=3。

• 第二次迭代

鍵：A[2]=4。

• 第三次迭代

鍵：A[3]=2。

• 第四次迭代

鍵：A[4]=1。

插入排序演算法的實現

#include <iostream>
using namespace std;

void insertion_sort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      int key = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = key;
      j--;
    }
  }
}

int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  insertion_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

插入排序演算法複雜度

時間複雜度

• 平均情況

平均來說，在插入排序的第 i 次傳遞中，會進行 i 次比較。所以，如果有 n 次迭代，那麼平均時間複雜度可以在下面給出。

1 + 2 + 3 + ... + (n-1) = n*(n-1)/2

因此時間複雜度為 [Big Theta]：O(n²)。

• 最壞情況

最壞的情況發生在陣列反向排序的時候，必須進行最大數量的比較和交換。

最壞情況下的時間複雜度為 [Big O]：O(n²)。

• 最佳情況

最好的情況發生在陣列已經排序的情況下，然後只執行外迴圈 n 次。

最佳情況下的時間複雜度為 [Big Omega]：O(n)。

空間複雜度

插入排序演算法的空間複雜度為 O(n)，因為除了一個臨時變數外，不需要額外的記憶體。