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

手撕排序Day2--希尔排序

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

手撕排序Day2--希尔排序

因为直接排序的元素集合越接近有序,插入排序的时间效率越高,因此希尔排序就是先让集合尽可能的接近有序,再进行一个插入排序。

我们还是将数组 arr[] = { 9,8,7,6,5,4,3,2,1 } 改为升序排列。

首先确定一个gap的值(这里取gap=3),让每隔gap-1的数进行比较并进行交换来进行一个预排序。这时再进行插入排序,就会快的多了。

但是如果数组中的较多的时候,比如数组中含有1亿个数,那么只交换一次再进行插入排序,并不能比插入排序快多少,因此我们需要调整gap的值。

因为gap的值越大,数组中大的值越快排到后面,小的数越快到前面,但是不接近有序。而gap的值越小,越接近有序,当gap等于1时,就是插入排序。因此我们可以取gap等于数组长度n或n/2等,并且在预排序时逐渐的减小gap的值,直到gap=1,就可以完成集合的排序。

时间复杂度到
稳定性不稳定
void ShellSort(int*arr,int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//防止gap为0,且最后一次执行时gap一定为1
		for (int i = 0; i < n - gap; i++)//最后gap个会在end+gap时被比较
		{
			int end = i;
			int tmp = arr[i + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end=end-gap;
				}
				else
					break;

			}
			arr[end + gap] = tmp;
		}
	}
}

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

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

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