插入排序

Harshit Jindal 2023年1月30日 2021年2月7日
  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 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