插入排序算法C/C++代码图文讲解

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

（1）步骤

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

（2）动图演示

（3）直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

（4）C语言代码实现如下：

#include <stdio.h>
#include <stdlib.h>
void InsertSort(int num[],int n)
{
    int i,j,k;
    for(i=1;i<n;i++)//默认第一个是有序的
    {
        k=num[i];//获取无序的元素
        for(j=i-1;j>=0;j--) //在有序队列中从后往前一个个的比
        {
            if(k>=num[j])//如果k比这个数大，就放在这个数的后面
            {
                num[j+1]=k;
                break;
            }
            num[j+1]=num[j];//如果k比这个数小，那就把这个数后移
            if(j==0)
                num[0]=k;
        }
    }
}

int main()
{
    int num[5]= {2,3,1,5,4};
    InsertSort(num,5);
    for(int i=0; i<5; i++)
    {
        printf("%d\n",num[i]);
    }
    return 0;
}

如果我们编译并运行上述程序，那么它应该产生以下结果：

1
2
3
4
5