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

直接插入排序,希尔排序

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

直接插入排序,希尔排序

文章目录
  • 插入排序
  • 希尔排序

插入排序

时间复杂度O(N*N)插入排序是稳定的
类似于摸牌的时候,一张一张摸,然后一张一张排序。

先来看一趟排序怎么排
首先把要排的数(x)存起来,然后跟前面排好的数组依次比较,遇到比x大的就覆盖掉x,再比较,直到遇到比x小的,或者循环结束,就停下来,把x的值再拿出来放到停下来的位置,算作一趟。
接下来就是怎么控制多次排序。
从头到尾遍历一遍即可

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int x = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = x;
	}

}
希尔排序

时间复杂度O(N*logN) 希尔排序是不稳定算法
是插入排序的大优化,希尔排序是将待排序的数组元素 按下标的一定增量分组 ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序;然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。

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


	while (gap > 1)
	{
		gap /= 2;

		//效率稍微高一点点
		//gap /= 3 + 1;


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

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

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

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