【学习分享】小白写算法之插入排序篇

前言
一、什么是插入排序算法
二、插入排序算法如何实现
三、C语言实现算法
四、复杂度计算
五、算法稳定性
六、小结

前言

要学好每个算法，我觉得需要先总结出规律，然后自己去推演一遍，加深记忆，否则的话很难真正领悟算法真谛，以后也很难实际去应用起来。所以沉下心来慢慢学，学会算法真的很有意思哈~

一、什么是插入排序算法

想象一下我们在打扑克，我们每拿到一张牌习惯于将其插入到手中的扑克中并按顺序排列，这个就是我们第一次接触到插入排序算法。
在这里插入图片描述
如下动图展示了从10到1的逆序序列如何进行插入排序到顺序序列的过程。

二、插入排序算法如何实现

我们设定一个序列{6,5,3,4,2,1}，第i轮需要做的事情是把第i个数插入到正确的位置。
在这里插入图片描述

插入到正确的位置怎么实现?
我们选择第3轮进行分析，分析见下图。
在这里插入图片描述

分析：
所以第3轮中一共执行了3次。
第1次4跟第2个（数组中计数从0位开始）数6比较，6大，所以6向右移动1位，在第2位插入4。
第2次4跟第1个数5比较，5大，所以5向右移动1位，在第1位插入4。
第3次4跟第0个数3比较，4大，所以4不移动，相当于在第1位插入4。第3轮排序结束。

其他依次类推，可以得出如下规律：
第i轮中一共执行了i次。
先记录一下第i个数为key。在i的范围内用参数j来指向每次比较位，j的初始值为i-1。
第i次key跟第j位的数进行比较，如果第j位的数＞key，那么第j位的数向右移动1位，然后在第j位插入key。
如果第j位的数≤key，那么不移动，在第(j+1)位插入key。
在这里插入图片描述
但是这样有个问题，就是插入key的位置不统一，为了统一插入key的位置，我们修改下如上的规律，改成下面的方式：
第i次key跟第j位的数进行比较，如果第j位的数＞key，那么第j位的数向右移动1位，先让j=j-1，然后在第(j+1)位插入key。
如果第j位的数≤key，那么不移动，在第(j+1)位插入key。(这样可以统一插入key的位置到j+1位)。
这个就是插入排序的算法了。

三、C语言实现算法

void insertionsort(int arr[],int n)   //插入排序算法
{
    for(int i=1;i<n;i++)
        {
            int key = arr[i];       //暂存第i位的数到参数key
            int j=i-1;              //从第i-1位开始和key进行比较
            while(j>=0 && arr[j]>key)   //关键语句，j=-1或者第j位比key要小退出循环
            {
                 arr[j+1] = arr[j];    //如果第j位＞key，那么第j位右移到第j+1位
                 j = j-1;              //j继续左移j=j-1;
            }
            arr[j+1] = key;            //在第j+1位插入暂存在key的第i位数值。
        }
}

加入打印后用gcc编译后运行，得到的结果也是符合预期的。
在这里插入图片描述
在《软件设计师教程》里算法是这样写的，这种写法和冒泡排序的写法很像，看个人选择。

void insertsort(int arr[],int n)
{
	int i,j;
	int tmp;
	for(i=1;i<n;i++)
	{	
        if(data[i]<data[i-1])  //如果第i位数≥第i-1位数，不移动。
        {
            tmp = data[i];     //如果第i位数＜第i-1位数，则插入到比第i位大的第j位。
            data[i] = data[i-1];
            for(j=i-1;j>=0 && data[j] > tmp;j++)
                data[j+1] = data[j];
            data[j+1] = tmp;
        }	
    }	
}