基本思想

直接插入排序的原理非常简单，即：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的序列上，直到对象全部插入为止。

典型的直接插入排序案例就是理扑克牌，你在抓牌的过程中就会对手上的扑克牌进行排序，找到每张牌需要插入的位置，然后进行插入。

图解排序过程

现有如下的一个序列(以从小到大排列为例)：
在这里插入图片描述
绿色部分是序列中的有序片段，我们从下标为4的位置开始直接插入排序，我们需要定义几个辅助变量：

变量i表示从i位置开始进行直接插入排序，变量temp用于临时存储i位置的元素值，变量j表示从j位置开始往前寻找i位置元素的插入位置，你也可以从下标0位置开始往后找插入位置。

首先让j位置元素与i位置元素比较，若j位置元素大于i位置元素，则需将j位置元素后移，因为后移j位置元素会覆盖i位置元素，所以先将i位置元素存放到变量temp：
在这里插入图片描述
然后让j前移，继续让j位置的元素与temp变量值比较，若大于，则继续后移：

再让j前移，比较j位置的元素与temp变量值，若大于，则继续后移；若小于，则已经找到插入位置：

插入位置为下标2，即：j + 1 位置。

原序列的前四个元素本来是有序的，现在经过了一轮比较，序列的前五个元素变得有序了，接下来就可以通过循环依次将后面的元素变得有序。

代码如下：

void InsertSort(SSTable t,int i){

	int temp,j,k;

	//将i位置元素值存放到temp变量

	temp = t.n[i];

	for(j = i;j <= t.length;++j){

		for(k = j - 1;k >= 0 && temp < t.n[k].key;--k){

			t.n[k + 1] = t.n[k];

		}

		t.n[k + 1] = temp;

	}

}

但这个算法有一个缺陷，就是每次比较都需要判断下标是否越界，这无疑增加了算法的负担，这在查找算法中已经提到过，我们可以采用带哨兵的序列来解决这一问题。

改进直接插入排序算法

在构建待排序序列时我们额外申请一个空间，用于存放哨兵，比如：
在这里插入图片描述
还是这个序列，前四个元素已经有序，我们将i位置的元素存入下标0作为哨兵，此时我们无需关系下标是否越界，只需要让j位置的元素不断地与哨兵位置元素进行比较。

若j位置元素大于哨兵位置元素，则j位置元素后移，j指针前移；若小于，则找到插入位置，插入位置仍然为j + 1，具体步骤和前面类似。

还有可以改进的地方，就是在插入排序之前，可以先比较一下i位置和i – 1位置的元素，若i位置的元素值大于i – 1位置的元素值，则说明i位置的元素就应该存放在i位置。因为i – 1位置的元素值是前面已经排好序的序列中的最大值，若待排序的元素值比它还大，说明待排序元素为最大值，那么放在最后就可以了，无需移动。

代码实现

先构建待排序序列：

typedef struct {

	int key;

}ElemType;



typedef struct{

	ElemType *n;

	int length;

}SSTable;



SSTable CreateTable(){

	SSTable st;

	st.n = (ElemType*) malloc(sizeof(ElemType) * 12);

	st.length = 11;

	st.n[1].key = 3;

	st.n[2].key = 5;

	st.n[3].key = 10;

	st.n[4].key = 16;

	st.n[5].key = 7;

	st.n[6].key = 32;

	st.n[7].key = 83;

	st.n[8].key = 23;

	st.n[9].key = 54;

	st.n[10].key = 29;

	st.n[11].key = 96;

	return st;

}

直接插入排序算法实现如下：

void InsertSort(SSTable t){

	int i,j;

	//从第二个元素开始插入

	for(i = 2;i <= t.length;++i){

		//将待插入元素放入哨兵位置

		t.n[0] = t.n[i];

		if(t.n[i].key < t.n[i - 1].key){

			//若待插入元素小于前一个元素值，则开始插入

			for(j = i - 1;t.n[0].key < t.n[j].key;--j){

				//从i - 1位置开始寻找插入位置

				t.n[j + 1] = t.n[j];

			}

			//将哨兵位置的元素插入到j + 1位置

			t.n[j + 1] = t.n[0];

		}

	}

}

性能分析

最好的情况，序列本身有序，则长度为n的序列需要比较n – 1次，无需移动元素。

最坏的情况，序列是逆序的，则长度为n的序列中，第一个元素无需操作，第二个元素需要比较一次，第三个元素需要比较两次，以此类推，第n个元素需要比较n – 1次。

则总共需要比较的次数为： $\frac{(n + 2)(n – 1)}{2}$ ；需要移动的次数为： $\frac{(n + 4)(n – 1)}{2}$ 。

综上所述，直接插入排序的时间复杂度为O(n²)。

对于空间复杂度，因为只借助了一个空的元素存储空间，所以空间复杂度为O(1)。

微信搜索【码视界】或者扫描下方二维码关注我的微信公众号，更多精彩等着你！

本篇文章来聊一聊直接插入排序。