栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

插入排序 希尔排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

插入排序 希尔排序

生活中时常需要用到排序:对班上成绩的高低排序,人的身高排序,对不同餐饮商家根据好评的高度进行排序...

接下来我会分两期介绍排序算法,不同的排序算法的时间和空间复杂度都有不同,我会在最后进行统一的计算。

1、插入排序

当我们在玩斗地主的时候,就会使用到插入排序,每次我们抽到一张牌,都需要在已有的牌中找到前一张牌比抽到牌小,且后一张牌比抽到的牌大的位置进行插入。

基本的思想就是,我们假设现在抽到第i张牌,并且前i-1张牌已经有序了,按照前面的思路。在前i-1个数中找到前一个数比第i个数小,并且后一个数比第i个数小的位置,插入第i个数。

这样就能保证i个数有序,不断归纳下去,最后抽到的牌总是有序的。

具体代码的实现是:定义一个tmp为第i个位置,End为第i-1个,将前i-1个数逐一和tmp比较,如果比tmp来的大,就往后移一位,然后End减-1往前走,这样就能比较完前i-1个数。

我们不妨先写一个单次的排序,再考虑整体排序。

void InsertSort(int* a, int n)
{
	//单趟的排序
	int End = n - 2;
	int tmp = a[n-1];
	while (End >= 0)
	{
		if (a[End] > tmp)
		{
			a[End + 1] = a[End];
			End--;
		}
		else
		{
            a[End+1] = tmp;//不满足条件就在End 后面插入tmp
			break;
		}
	}
}

这样还有一点小问题,就是End等于0如果进到第一个循环内部,那么End减一以后小于0,跳出循环后,数并没有插入。

我们可以这样修改,不管是循环跳出,还是进入else条件,都要在End后面插入,不妨直接在while循环后面插入。

void InsertSort(int* a, int n)
{
	//单趟的排序
	int End = n - 2;
	int tmp = a[n-1];
	while (End >= 0)
	{
		if (a[End] > tmp)
		{
			a[End + 1] = a[End];
			End--;
		}
		else
		{
			break;
		}
	}
          a[End+1] = tmp;//不满足条件就在End 后面插入tmp
}

整体的循环我们不能从最后一个开始,因为我们排第i个数的前提是前i-1个数需要有序,所以必须从头排序,保证前面的数有序。

void InsertSort(int* a, int n)
{
	for(int i = 1;i= 0)
	    {
		    if (a[End] > tmp)
		    {
			    a[End + 1] = a[End];
			    End--;
		    }
		    else
		    {
		    	break;
		    }
	    }
        a[End+1] = tmp;//不满足条件就在End 后面插入tmp
    }
}

我们拿一个数组来测试一下:

我们浅计算一下它的时间复杂度,考虑最坏的情况,如果数组是逆序,那么第i个数都要比较i-1次,加和后的时间复杂度是O(N^2)。如果数组已经是有序,或者是部分有序,那么这种情况下的插入排序效率很高,是O(N)。

所以我们如果想要提高插入排序的效率,要做的就是让数组部分有序。

2.希尔排序(Shell Sort)

 希尔排序是在插入排序的基础上进行了一步预处理,而预处理的目的,就是为了达到数组的部分有序。

预排序的步骤就是把一个数组分成gap组,下面我们先假设gap = 3,对这gap个组的数据分别进行插入排序。

 如果gap比较大,就可以让大的数据很快的到后面,当我们的数据个数不断加大,开始的时候需要gap很大,后面逐渐让gap变小,最后可以达到基本有序。

单趟排序的思路和上面的插入排序一样——

for (int i = 0;i < n - gap;++i)
		{
			int End = i;
			int tmp = a[End + gap];
			while (End >= 0)
			{
				if (a[End] > tmp)
				{
					a[End + gap] = a[End];
					End -= gap;
				}
				else
				{
					break;
				}
			}
			a[End + gap] = tmp;
		}

实际上gap的取法很多样,这导致了希尔排序的时间复杂度十分难计算。我们每次循环都让gap模3加1——这样能保证最后一次gap必定是1,从而是插入排序。

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap/3 +1;
		for (int i = 0;i < n - gap;++i)
		{
			int End = i;
			int tmp = a[End + gap];
			while (End >= 0)
			{
				if (a[End] > tmp)
				{
					a[End + gap] = a[End];
					End -= gap;
				}
				else
				{
					break;
				}
			}
			a[End + gap] = tmp;
		}
}

接下来引用殷人昆老师的数据结构书中的一段分析:

 

我们对gap的取法和Knuth一样,所以时间复杂度大概在O(N^1.25)~O(1.6*O^1.25)。这相对插入排序已经优化了很多。 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970650.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号