插入排序与希尔排序

2017-12-09 | Have been read： times

今天刚参加了华中师范大学的ACM新生杯，趁着还保持着对算法的敏感度（虽然今天A的题没有几道是真正的算法题），来写一篇关于插入排序及其升级版算法希尔排序的介绍
部分内容取自于知乎用户彭湖湾的文章

概念

插入排序即将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。一般此算法时间复杂度较高，故适用于少量数据的排序

插入排序(1.0)

插入排序1.0即直接插入排序，将已知有序序列遍历一遍，以找到插入元素的位置，将该位置面的元素全部向后移动一位。

具体实现步骤:(对待插入元素)

和相邻的左边元素的值比较大小
如果左边元素大于待排序元素，则交换两者的值，左边元素的值“右移”一位。
如果左边元素小于等于待排序元素，说明已经插入到“合适位置”了，一趟插入结束。

示例如下图：

插入排序1.0

时间复杂度： $O(n^2)$

实现代码如下：

//a[0]中存的是a数组的长度
void insertsort(int *a)
{
	n = a[0];
	for(int i=2;i<=n;i++)
	{
		int t = a[i];
		int j = i;
		while(j>0&&t<a[j-1])
		{
			a[j]=a[j-1];
			j--;
		}
		a[j]=t;
	}
}

插入排序(2.0)

插入排序2.0即对待插入元素在已知有序序列中找到位置的过程进行了优化。
既然序列是已知的、有序的，那么我们自然可以想到在这过程中使用二分法。

代码如下：

//x是待插入元素的值
void binaryq(int *a,int l,int r,int x)
{
	int mid;
	while(l<=r)
	{
		mid = (l+r)/2;
		if(x>a[mid])
		{
			l = mid+1;
		}else{
			r = mid-1;
		}
	}
	return l;
}

void insertsearch2(int *a)
{
	int n = a[0];
	for(int i=2;i<=n;i++)
	{
		int t = a[i];
		int l = binaryq(a,0,i-1,a[i]);
		for(int j=i;j>l;j--)
		{
			a[j]=a[j-1];
		}
		a[l]=t;
	}
}

希尔排序(插入排序 3.0)

希尔排序又被称为步长递减插入排序或增量递减插入排序。

设h为步长，那么希尔排序的基本步骤为：

选择一个递增序列。并在递增序列中，选择小于数组长度的最大值，作为初始步长 h。
开始的时候，将数组分为h个独立的子数组(1中h)，每个子数组中每个元素等距离分布，各个元素距离都是h。
对2中分割出的子数组分别进行插入排序
第一轮分组的插入排序完成后，根据递增序列（逆向看）减少h的值并进行第二轮分组，同样对各个子数组分别插入排序。不断循环1、2、4, 直到h减少到1时候，进行最后一轮插入排序，也就是针对整个数组的直接插入排序（这个时候分组只有1个，即整个数组本身）
一开始的时候h的值是比较大的（例如可以占到整个数组长度的一半），所以一开始的时候子数组的数量很多，而每个子数组长度很小。随着h的减小，子数组的数量越来越少，而单个子数组的长度越来越大。

代码如下：

void shellsort(int *a)
{
	int n = a[0];
	int h = 1;
	while(h<n/3)h=3*h+1;//选择步长
	while(h>=1)
	{
		for(int i=h;i<=n;i++)
			for(int j=i;j>=h;j-=h)
				if(a[j]<a[j-h])
				{
					int t=a[j];
					a[j]=a[j-h];
					a[j-h]=t;
				}
		h/=3;
	}
}