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

排序sort——未完成

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

排序sort——未完成

插入排序 直接插入排序

单次插排:
那么,对于一个数组,可以从a[0]开始,直至a[sz-1],进行插入排序。

注意:end的值最大为sz-1-1,超过会越界。
时间复杂度:O(N^2),逆序的情况。
但最好的情况为O(N),相比之下,优于冒泡排序。
当序列越趋向于有序,该排序就越好。

代码实现
void InsertSort(int* a, int sz)
{
	assert(a);
	for (int i = 0; i < sz - 1; i++)
	{
		//[0,end]有序,再插入后一个值还保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{	
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}
希尔排序

希尔排序是直接插入排序的小变形。
先进行预排序,使数列接近于有序,再进行直接插入排序。

代码实现:
注:gap和sz有直接关系

//排升序,gap越大,大的数更快到后面,小的更快到前面,但越不接近有序
//排升序,gap越小,越接近有序;gap=1时,就是直接插入排序

void ShellSort(int* a, int sz)
{
	int gap = sz;

	while (gap > 1)
	{
		//分组
		gap = gap / 3 + 1;//保证最后一次一定 =1 

		for (int i = 0; i < sz - gap; i++)
		{
			//单趟
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/943669.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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