直接插入排序

1、直接插入排序（Straight Insertion Sort）

---- 直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

2、算法实现

#define MaxSize 10	//要排序数组元素的最大值，可根据需要修改
typedef struct 
{
	int r[MaxSize+1];//用于存储要排序数组，r[0]用作哨兵或临时变量
	int length;	//用于记录顺序表的长度
}SqList;

void swap(SqList *L,int i,int j)
{
	int t = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = t;
}
void InsertSort(SqList *L)
{
	int i,j;
	for(i=2;ilength;i++)
	{
		if(L->r[i]r[i-1]) //需将L->r[i]插入有序子表
		{
			L->r[0] =L->r[i]; //设置哨兵，将L->r[i]保存起来，前面数据要后移，会覆盖
			for(j=i-1;L->r[j]>L->r[0] && j>0;j--)
				L->r[j+1] = L->r[j]; //凡是比哨兵大的值都后移
			L->r[j+1] = L->r[0];	//插入到正确的位置

		}
	}

}
int main()
{
	SqList *L = (SqList*)malloc(sizeof(SqList));
	int a[MaxSize] = {9,1,5,8,3,7,4,6,2,0};
	for(int i=0;ir[i+1] = a[i];
	}
	L->length = MaxSize;
	InsertSort(L);
	cout<<"排序后的序列如下："<<endl;
	for(int i=1;ilength;i++)
	{
		cout<r[i]<<" ";
	}
	cout<<endl;
	system("pause");
	return 0;
}

算法分析：从空间上看，该算法只需要一个记录的辅助空间，关键是看它的时间复杂度。

最好的情况：要排序的表本身就是有序的，比较次数n-1次，没有数据移动。时间复杂度是O(n).

最坏的情况：待排序表是逆序的，此时需要比较2+3+...+n=(n+2)(n-1)/2，记录的移动次数也达到最大值，

3+4+...+n+1=(n+4)(n-1)/2次。如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动的次数

约为n^2/4次，所以直接插入排序法的时间复杂度是O(n^2)。