数据结构笔记 - 排序算法 直接插入排序算法

直接插入排序：

将一个元素通过和当前已经排序好的数组的最大元素进行比较，并在待插入数组较小的情况下通过设置哨兵，整体移动，插入正确位置的步骤，从此得到一个新的排序好的数组的过程。

#include <stdio.h>

#define MAXSIZE 100  /* 待排序数组的大小 */

typedef struct
{
	int r[MAXSIZE+1];	/* 待排序数组r，r[0]为哨兵或临时变量 */
	int length;			/* 待排序数组的长度，为了方便理解，不包含r[0]元素 */
}SortList;

/* 直接插入排序算法 */
void InsertSort(SortList *L)
{
	int i,j;
	for(i=2;i<=L->length;i++)
	{
		/* 将r[i]插入有序数组前进行判断 */
		if (L->r[i]<L->r[i-1])
		{
			L->r[0]=L->r[i];	/* 设置哨兵 */
			for(j=i-1;L->r[j]>L->r[0];j--)
				/* 循环向右移动数据元素 */
				L->r[j+1]=L->r[j];
			L->r[j+1]=L->r[0]; /* 把r[i]（此时存在r[0]中）插入到循环移动腾出的位置 */
		}
	}
}

直接插入排序时间复杂度分析：

最好的情况下，即每次需要插入的元素都是最大的，这样只需要比较n-1次，没有移动记录，所以时间复杂度为O(n)。

最坏的情况下，即待排序的是逆序的，此时需要比较的次数为：2+3+4+…+n=(n+2)(n-1)/2，而移动的次数为：(n+4)(n-1)/2。总得时间复杂度为O(n^2)。

直接插入排序算法比冒泡和简单排序算法的性能要好一点。