插入排序

〇、返回

一、概述

插入排序是一种简单直观的比较类排序算法。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序适用于少量数据的排序，时间复杂度为O($n^2$)，是稳定的排序方法。

二、工作原理

插入排序的基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，直到整个数据变成有序序列。

三、算法步骤

1. 初始化：假设数组的第一个元素是一个已排序的子数组。

2. 遍历数组：从第二个元素开始，将其与已排序的子数组进行比较。

3. 比较和插入：

    将当前元素与已排序子数组中的元素从后向前逐一比较。

    如果当前元素小于已排序子数组中的某个元素，则将该元素向后移动一位。

    重复上述步骤，直到找到合适的位置插入当前元素。

4. 重复步骤2-3：对数组中的每个元素重复上述步骤，直到整个数组排序完成。

四、代码示例（C++）

#include<bits/stdc++.h>

using namespace std;

int main() {

    int n;

    cin>>n;

    vector<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;

        // 在已排序的部分中找到插入位置

        while (j>=0 and a[j]>key) {

            a[j+1]=a[j];        // 向后移动元素

            j--;

        }

        a[j+1]=key;        // 插入元素

    }

    for (int i=0;i<n;i++) {

        cout<<a[i]<<" ";

    }

    cout<<"\n";

    return 0;

}

时空复杂度及稳定性

时间复杂度

最好情况：O(n)（当输入数组已经是排序好的）

最坏情况：O($n^2$)（当输入数组是逆序的）

平均情况：O($n^2$)

空间复杂度

O(1)（原地排序）

稳定性

插入排序是稳定的排序算法，即相等的元素的相对顺序在排序后不会改变。

总结

插入排序是一种简单且直观的排序算法，特别适用于小规模数据或部分有序的数据。它的实现简单，易于理解，但在大规模数据排序时效率较低。插入排序的一个重要特性是其稳定性，这在某些应用场景中非常重要。尽管插入排序的时间复杂度在最坏情况下为O($n^2$)，但在实际应用中，对于小规模数据或接近有序的数据，插入排序仍然表现出良好的性能。