当前位置: 首页 > article >正文

115.【C语言】数据结构之排序(希尔排序)

目录

1.希尔排序(又称缩小增量排序)(插入排序的优化版本)

过程1:预排序

过程2:插入排序

2.代码

预排序代码

1.一次排一组(时间复杂度比第二种写法高)

运行结果

其他写法

2.一次排多组(多组并排)

运行结果

希尔排序代码

1.当预排序一次排一组时

运行结果

2.当预排序一次排多组时

运行结果

gap的其他变化方式


1.希尔排序(又称缩小增量排序)(插入排序的优化版本)

希尔排序(Shell's Sort):分为两个过程:预排序和直接插入排序

过程1:预排序

作用:让数组接近于有序状态

方法:分组插入排序(即对每组数字插入排序),例如间隔gap为一组

以升序为例,如数组int* arr[]={9,1,2,5,7,4,8,6,3,5}; ,设gap==3,即分三组插入排序

第一组:9,5,8,5(相互间隔gap步);第二组:1,7,6(相互间隔gap步);第三组:2,4,3(相互间隔gap步)

第一组插入排序后:5,5,8,9;第二组插入排序后:1,6,7;第三组插入排序后:2,3,4

排序后,小数尽量靠前,大数尽量靠后

过程2:插入排序

相对于只进行插入排序而言,由于预排序已经将数组接近于有序状态,因此预排序后的插入排序执行的会非常快

2.代码

gap取多少合适呢?

gap越大,跳的越快,越不接近有序(例如gap==n)

gap越小,跳的越慢,越接近有序(例如gap==1)

希尔没有给出具体的数字,gap为动态的值最合适,依循环次数而定,常见的有两种情况

gap = gap / 2;

//或

gap = gap / 3 + 1;//Knuth在《计算机程序设计技巧》给出的式子

和之前一样,先写单趟预排序,某次循环后例如gap=3

预排序代码

分组后,a[end]后一个元素应该间隔gap,因此int tmp = arr[end + tmp]

	while (end>=0)
	{
		if (tmp < arr[end])
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	arr[end + gap] = tmp;

再将while循环套到for循环中来控制每次循环的end的值

这样预排序就有两种写法:

1.一次排一组(时间复杂度比第二种写法高)

对于上图而言,把绿色组排有序了后再去排蓝色组,把蓝色组排有序了后再去排紫色组,显然需要三重循环(每组排有序2重循环,控制组一重循环)

int gap = 3;//将arr分为三组预排序
for (int j = 0; j < gap; j++)//j控制组
{
	for (int i = j; (j==0)?i<n:i<n-gap+j; i += gap)//i控制每组的排序
	{
		int end = i - gap;
		int tmp = arr[end + gap];//arr[end+gap]的值已被tmp保存,数组元素的值可以向右覆盖
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		arr[end + gap] = tmp;
	}
}

注意到i循环条件的写法:(j == 0) ? i < n : i < n - gap + j; (原因在:int end = i - gap;,i的值跟随end+gap)

对于gap==3的情况,j==0,i最多到n-1;j==1,i最多到n-2;;j==1,i最多到n-1,找规律即可写出上述判断条件

运行结果

预排序后,按分组看每一组都是升序的:{1,4,7,9}、{0,6,7}、{-1,2,3}

 

其他写法
		int gap = 3;
		for (int j = 0; j < gap; j++)//j控制组
		{
			for (int i = j; i < n - gap; i += gap)//i控制每组的排序
			{
				int end = i;//end的值跟随i
				int tmp = arr[end + gap];//arr[end+gap]的值已被tmp保存,数组元素的值可以向右覆盖
				while (end >= 0)
				{
					if (tmp < arr[end])
					{
						arr[end + gap] = arr[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				arr[end + gap] = tmp;
			}
		}

为什么i的循环条件变简单了呢?因为int end=i;中i的值跟随end(***推荐写法***),不同于之前的写法

2.一次排多组(多组并排)

对于上图而言,预排序可以交替进行:绿色组-->蓝色组-->紫色组-->绿色组-->蓝色组-->紫色组->绿色组-->蓝色组-->紫色组-->......只需要两重循环 

	int gap = 3;
	for (int i = gap; i < n; i++)//交替排序,每次i+1
	{
		int end = i - gap;
		int tmp = arr[end + gap];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		arr[end + gap] = tmp;
	}
运行结果

希尔排序代码

由于预排序有整体上有两种写法,因此希尔排序代码也有两种写法

希尔排序的框架(以gap /= 2为例)

void ShellSort(int* arr, int n)
{
	int gap = n;
    while (gap > 1)
	{
		gap /= 2;
        //这里写预排序的代码
    }
}

1.当预排序一次排一组时

以gap /= 2为例,初始gap==n,无论n取何值,最后一次循环gap==1,没有必要调用InsertSort

原因:任何一个数gap/2/2/2/2/2/2/2/2/2/2...的最终结果都是1

即gap>1为预排序,gap==1为直接插入排序

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
	    for (int j = 0; j < gap; j++)//j控制组
		{
			for (int i = j; i < n - gap; i += gap)//i控制每组的排序
			{
				int end = i;//end的值跟随i
				int tmp = arr[end + gap];//arr[end+gap]的值已被tmp保存,数组元素的值可以向右覆盖
				while (end >= 0)
				{
					if (tmp < arr[end])
					{
						arr[end + gap] = arr[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				arr[end + gap] = tmp;
			}
		}
	}
}
运行结果

但写四重循环很麻烦,不推荐这样写

2.当预排序一次排多组时

以gap = gap / 2为例,初始gap==n

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = gap; i < n; i++)//交替排序,每次i+1
		{
			int end = i - gap;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}
运行结果

gap的其他变化方式

gap = gap/3 + 1,对于任何一个数n,其n/3/3/3/3/3/3/3/3/3.....结果不为0前,三种可能:1或2,若为gap = gap/3 + 1保证循环结束后gap==1(2/3+1==1,1/3+1==1,0/3+1==1)


http://www.kler.cn/a/446207.html

相关文章:

  • 两点间最短距离 - Dijkstra
  • springboot中的AOP以及面向切面编程思想
  • APM32F411使用IIS外设驱动es8388实现自录自播
  • 中国新能源汽车公共充电桩数据合集(2002-2023年)
  • 设计模式12:状态模式
  • 详解 Qt WebEngine 模块
  • 纯血鸿蒙APP实战开发——应用新功能引导实现案例
  • 第P3周:Pytorch实现天气识别
  • linux-----网络编程
  • 【C++ 真题】P1996 约瑟夫问题
  • Python中的上下文管理器:从资源管理到自定义实现
  • 双臂机器人
  • Flutter 多个弹窗关闭指定弹窗
  • Vue.js前端框架教程13:Vue空值合并?? 可选链?.和展开运算符...
  • 域名和服务器是什么?域名和服务器是什么关系?
  • Verilog的testbench中模块实例化方法
  • 【网络安全】用 Frida 修改软件为你所用
  • 2025年前端面试热门题目——HTML|CSS|Javascript|TS知识
  • linux-多线程
  • 随手记:微信小程序穿透组件样式穿不过去,样式隔离
  • 【Spring】Spring的模块架构与生态圈—数据访问与集成(JDBC、ORM、Transactions)
  • ML 系列:第 41节 - 假设检验简介
  • html+css网页设计 旅游 移动端 雪花旅行社4个页面
  • 数据库基础-索引
  • Windows11 家庭版安装配置 Docker
  • 11_HTML5 拖放 --[HTML5 API 学习之旅]