插入排序

Harshit Jindal 2023年10月12日
  1. 插入排序演算法
  2. 插入排序示例
  3. 插入排序演算法的實現
  4. 插入排序演算法複雜度
插入排序

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

插入排序演算法

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

  • 我們將未排序子陣列 A[1] 中的第一個元素標記為鍵。
  • 然後將鍵與排序子陣列中的元素進行比較,這裡我們只有一個元素,A[0]
  • 如果鍵大於 A[0],我們將其插入 A[0] 之後。
  • 否則,如果它小於 A[0],我們再比較一下,把它插入到 A[0] 之前的正確位置。(在 A[0] 的情況下,只有一個位置)
  • 將下一個元素 A[2] 作為鍵。將其與排序後的子陣列元素進行比較,並在比 A[2] 小的元素後插入。如果沒有小元素,則將其插入到排序子陣列的開頭。
  • 對未排序子陣列中的所有元素重複上述步驟。

插入排序示例

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

排序子陣列 未排序子陣列 陣列
( 5 ) ( 3, 4, 2, 1) (5, 3, 4, 2, 1)
  • 第一次迭代

鍵:A[1]=3。

排序子陣列 未排序子陣列 陣列
( 3 , 5) (4, 2, 1) (3, 5, 4, 2, 1)
  • 第二次迭代

鍵:A[2]=4。

排序子陣列 未排序子陣列 陣列
( 3, 4, 5) (2, 1) (3, 4, 5, 2, 1)
  • 第三次迭代

鍵:A[3]=2。

排序子陣列 未排序子陣列 陣列
( 2, 3, 4, 5) (1) (2, 3, 4, 5, 1)
  • 第四次迭代

鍵:A[4]=1。

排序子陣列 未排序子陣列 陣列
( 1, 2, 3, 4, 5) () (1, 2, 3, 4, 5)

插入排序演算法的實現

#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(n2)。

  • 最壞情況

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

最壞情況下的時間複雜度為 [Big O]:O(n2)。

  • 最佳情況

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

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

空間複雜度

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

作者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Sort Algorithm