Dark`Kris

Private blog

I'm spark , hope you fire


插入排序与希尔排序

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

概念

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

插入排序(1.0)

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

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

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

示例如下图:

插入排序1.0

时间复杂度:

实现代码如下:

//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为步长,那么希尔排序的基本步骤为:

  1. 选择一个递增序列。并在递增序列中,选择小于数组长度的最大值,作为初始步长 h。
  2. 开始的时候,将数组分为h个独立的子数组(1中h), 每个子数组中每个元素等距离分布,各个元素距离都是h。
  3. 对2中分割出的子数组分别进行插入排序
  4. 第一轮分组的插入排序完成后,根据递增序列(逆向看)减少h的值并进行第二轮分组, 同样对各个子数组分别插入排序。 不断循环1、2、4, 直到h减少到1时候, 进行最后一轮插入排序,也就是针对整个数组的直接插入排序(这个时候分组只有1个,即整个数组本身)
  5. 一开始的时候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;
	}
}

希尔排序图示

h=5
h=2
h=1

希尔排序

时间复杂度:

本文章到此为止,谢谢阅读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading