插入排序

Posted on Edited on In

题目描述
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。

输入格式
输入共 2 行，第一行是一个整数 n，表示数组的长度。第二行包含 n 个整数，表示待排序的数组。

输出格式
输出共 1 行，包含 n 个整数，表示排序后的数组（升序排列）。

数据范围
1 ≤ n ≤ 1000
-1000 ≤ 数组元素 ≤ 1000

输入样例：

1
2
7
9 8 7 6 5 4 3

输出样例：

1
3 4 5 6 7 8 9

注意事项

  • 插入排序的时间复杂度为 O(n²)，空间复杂度为 O(1)。
  • 插入排序是稳定的排序算法。
  • 插入排序特别适合于小规模数据或基本有序的数据。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    // 插入排序
    for (int i = 1; i < n; i++)
    {
        int key = a[i]; // 保存当前要插入的元素
        int j = i - 1;
        // 将比key大的元素向后移动
        while (j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key; // 将key插入到正确的位置
    }
    
    // 输出排序后的数组
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(n²)，其中 n 为数组的长度。
  • 空间复杂度：O(1)。

代码解释

  • 我们从第二个元素开始，将其视为要插入的元素。
  • 对于每个要插入的元素，我们将其与已排序部分从后向前比较。
  • 如果已排序部分的元素大于当前要插入的元素，则将其向后移动一位。
  • 重复上述过程，直到找到一个小于或等于当前要插入元素的位置，或者到达数组的开头。
  • 将当前要插入的元素放到找到的位置上。
  • 重复上述过程，直到所有元素都被插入到正确的位置。