插入排序 – 算法

1、将排序部分分成两部分

2、每次从后面部分取最前面的数插入到前面部分的适当位置

该处提供两个插入排序版本，指定间隔插入与插入排序。后面对指定间隔排序提到Shell排序中的n/2间隔与Sedgewick间隔

例如：

排序前：92 77 67 8 6 84 55 85 43 67

[77 92] 67 8 6 8455 85 43 67 将77插入92前

[67 77 92] 8 6 8455 85 43 67 将67插入77前

[8 67 77 92] 6 8455 85 43 67 将8插入67前

[6 8 67 77 92] 8455 85 43 67 将6插入8前

[6 8 67 77 84 92]55 85 43 67 将84插入92前

[6 8 55 67 77 8492] 85 43 67 将55插入67前

[6 8 55 67 77 84 8592] 43 67 ......

[6 8 43 55 67 77 8485 92] 67 ......

[6 8 43 55 67 67 7784 85 92] ...... 

// 插入排序
int InsertionSort(int a[],int lens)
{
	int k;
	int tmp;
	for(int i=1;i<lens;i++)
	{
		int j=i-1;
		//取出待插数据
		tmp = a[i];
		
		// 遍历前面已排好序的序列，找插入位置
		// 在i之前查找需待插入数据a[i]的位置k
		for(k=j;k>=0;k--)
		{
			if(tmp<a[k]) a[k+1]=a[k];// 后移
			else break;//找到位置

		}
		// 找到位置，插入指定值
		if(i!=(k+1))a[k+1]=tmp;
	}
	return 0;
}

// 插入排序 - 使用指定间隔的
int InsertionSortWithGap(int a[],int lens,int gap)
{
	int k,tmp;
	// 控制插入层
	for(int m=0;m<gap;m++)
	{
		for(int i=gap+m;i<lens;i+=gap)
		{
			int j=i-gap;
			tmp=a[i];
			for(k=j;k>=0;k-=gap)
			{
				if(tmp<a[k]) a[k+gap]=a[k];
				else break;
			}
			if(i!=(k+gap))a[k+gap]=tmp;
		}
	}
	return 0;
}