插入排序算法

1、基本思想

        插入排序是一种简单直观的排序算法。它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。想象我们在整理一副扑克牌，每次拿到一张新牌，就将它插入到已经排好序的手牌中的合适位置，使得手牌始终保持有序的状态。

2、算法步骤

2.1、算法步骤描述：

以升序排序为例：

1、从第一个元素开始进行排序，第一个元素可以认为已经被排序过。

2、取下一个元素，在已经排序的元素序列中从后向前扫描一遍。

3、如果当前扫描到的已排序元素大于新元素，则将该已排序元素向后移动一位。

4、重复步骤 3，直到找到一个已排序元素小于或等于新元素。

5、将新元素插入到这个已排序元素位置的下一个位置。

重复步骤 2 到 5，不断进行扫描和插入操作以扩大有序序列，直到所有元素都被插入到合适的位置，完成排序。

2.2、插入排序算法动态演示图：

动态演示图来源网站URL：​​​​​​https://visualgo.net

3、代码实现

c语言代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
void sort(int arr[])
{
    int i, j;
    for(i = 1; i < N; i++)
    {
        int temp = arr[i]; //这轮要插入的数据
        j = i - 1; //要从这个位置往前遍历
        while(j >= 0 && arr[j] > temp)//寻找插入位置
        {
            arr[j+1] = arr[j];//后移 
            j--;
        }
        arr[j+1] = temp;//插入
    }
}
int main(int argc, char *argv[])
{
    srand(time(NULL));
    int a[N];
    int i;

    puts("排序前数组为：");
    for(i = 0; i < N; i++)
    {
        a[i] = rand()%100;//为数组随机赋值
        printf("%d ",a[i]);//输出排序之前数组值
    }
    puts("");

    sort(a);//排序

    puts("排序后的数组为：");
    for(i = 0; i < N; i++)
    {
        printf("%d ",a[i]);//输出排序之后的数组值
    }
    puts("");

    return 0;
}

4、时间复杂度和空间复杂度

平均时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

5、适用情况

1、数据量较小的情况下可以考虑使用插入排序。

2、待排序数据中有部分有序数据时，插入排序的效率会提高。