插入排序

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)，因为除了一个临时变量外，不需要额外的内存。