【数据结构初阶】希尔排序

鼠鼠最近学习了希尔排序，做个笔记！

希尔排序也是插入排序的一种捏！本篇博客也是用排升序来举例捏！

希尔排序是基于直接插入排序的，是由大佬D.L.Shell提出的。

目录

1.希尔排序

1.1.预排序

1.2.直接插入排序

2.希尔排序的时间复杂度

3.希尔排序和直接插入排序的性能比较

1.希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。如果不好懂没关系，继续看下面讲解：

鼠鼠上一篇博客介绍了直接插入排序应用时待排序的数组越接近有序，直接插入排序算法的时间效率越高。基于这个，D.L.Shell将希尔排序分为预排序和直接插入排序！

1.1.预排序

对待需排序的乱序数组，D.LShell不直接使用直接插入排序。他先搞一搞预排序。

预排序：

首先需排序的乱序数组分成gap组（若干组）。举个栗子吧：

让所有距离为gap的数分为一组，如图举例分为了gap=3组：蓝色组、红色组和绿色组。 

然后分别将蓝色组、红色组和绿色组的数据进行直接插入排序，这样每组数据排列都有序了，如图：

预排序其实大有作用，它能让待排序的乱序数组中大的数据尽量往后靠，让小的数据尽量往前靠，这样的话待排序的乱序数组就更接近有序。

那么我们来看看代码的推理过程：

1.我们先搞定蓝色组的直接插入排序的“单趟”：

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

 2.同样我们用循环控制好end就搞定了蓝色组的直接插入排序：

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

3.但是我们有gap组需要直接插入排序，那么我们再套一层循环循环gap次让不同组直接插入排序即可搞定预排序：

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

这种写法是让同一组直接插入排好再排下一组。

 鼠鼠下面再展示一种写法，其实与上面写法本质是一样的：

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

这种写法其实是多组并列插入排序 ，老爷们体会一下，鼠鼠很难解释捏！

预排序的代码我们暂且写到这里，我们可以看到：gap越大，大的数据越快往后靠，小的数据越快往前靠；但是需排序乱序数组整体越不接近有序。gap越小，则相反；当gap小到等于1时，就是直接插入排序，能让需排序乱序数组直接变成有序的。

1.2.直接插入排序

我们经过一次预排序是不是直接就让需排序乱序数组来直接插入排序呢？

其实不是的，因为经过一次预排序不能保证需排序乱序数组接近有序，只能保证比没有预排序之前更加有序，经过一次预排序就直接让需排序乱序数组来直接插入排序的话效率没有多大提升！

而且如果只进行一次预排序的话，gap就是一个定值，gap是定值是不合适的。如果gap确定是3，但需排序乱序数组数据个数有10000个的话，每组就有300多个数据要排，不合适！

其实主流玩法已尽解决了这些个问题，只要进行多组预排序就行，我们来看希尔排序的完整代码再分析：

//希尔排序排升序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < n - gap; j ++)
		{
			int end = j;
			int tmp = a[end + gap];
			for (end; end >= 0; end -= gap)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

这样子我们将gap设置成变化的，gap会越来越小，当gap不等于1时是预排序。相当于第一轮预排序大概是3个数据为一组排；第二轮预排序大概是9个数据为一组排；第三轮预排序是27个数据为一组排……而且每一轮预排序过后就越有序。

我们再分析发现，gap一定会变成1，那就是让需排序乱序数组直接来一把直接插入排序，这把直接插入排序过后循环结束并且需排序乱序数组就变成有序的了，而且经过了多次预排序最后来一把直接插入排序时间效率会很高！

当然gap如何变化都没有规定，我们也可以写成gap=gap/2……反正要保证最后一次循环的时候gap要等于1，才能保证最后一把是让需排序乱序数组整体进行直接插入排序。

我们来试试希尔排序得不得行：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

//希尔排序排升序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < n - gap; j ++)
		{
			int end = j;
			int tmp = a[end + gap];
			for (end; end >= 0; end -= gap)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

int main()
{
	int a[] = { 1,5,8,7,9,6,48,3,5,99,6,3,7,5 };
	PrintArray(a, sizeof(a) / sizeof(a[0]));
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

结果是没问题的！

2.希尔排序的时间复杂度

希尔排序有太多不确定性，所以时间复杂度不好计算，大多数人认为是O(N^1.3)。

3.希尔排序和直接插入排序的性能比较

也许老爷们会认为希尔排序弄那么多次预排序加一次直接插入排序，时间效率所不定还不如直接插入排序来的好。

其实不然，我们用一个程序比较比较就可以看出结果，这个程序用到一个C语言库里面的函数clock，clock函数的大致作用是获取从系统启动到调用这个clock函数之间的毫秒数。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

//希尔排序排升序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < n - gap; j ++)
		{
			int end = j;
			int tmp = a[end + gap];
			for (end; end >= 0; end -= gap)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

//直接插入排序排升序
void InsertSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		int end = j;
		int tmp = a[end + 1];
		for (end; end >= 0; end--)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

int main()
{
	int n = 100000;
	int* a1 = (int*)malloc(sizeof(int) * n);
	int* a2 = (int*)malloc(sizeof(int) * n);
	srand((unsigned int)time(0));
	for (int i = 0; i < n; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}

	int begin1 = clock();
	ShellSort(a1, n);
	int end1 = clock();

	int begin2 = clock();
	InsertSort(a2, n);
	int end2 = clock();

	printf("ShellSort:%d\n", end1 - begin1);
	printf("InsertSort:%d\n", end2 - begin1);
	return 0;
}

我们看到结果，排序10万个一模一样的随机数，希尔排序用22毫秒，而直接插入排序用4490毫秒！ 

感谢阅读！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/596315.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

jpg和png格式如何互相转换？这四个方法教会你！

jpg和png格式如何互相转换？这四个方法教会你！

JPG转PNG的转换是一个常见的图像处理需求&#xff0c;无论是因为PNG格式具有更好的透明度和无损压缩的特性&#xff0c;还是因为某些特定的应用场景需要这种格式。下面&#xff0c;我们将详细介绍如何将JPG转换为PNG格式&#xff0c;包括使用图像处理软件、在线转换工具、PDF转…
阅读更多...
Redis的数据类型及使用场景

Redis的数据类型及使用场景

redis命令大全官网: Commands | Docs (redis.io) 基本介绍 redis起初主要就是为了解决性能问题的&#xff0c;那么redis为什么快? 基于内存操作的&#xff0c;所以操作不需要跟磁盘进行交互&#xff0c;单次的执行会很快 命令执行是单线程 因为基于内存操作 单次执行时间反…
阅读更多...
【MicroPython ESP32】ssd1306驱动0.96“I2C屏幕汉字显示示例

【MicroPython ESP32】ssd1306驱动0.96“I2C屏幕汉字显示示例

所需模块micropython-ssd1306模块 中文下载站&#xff1a;https://www.cnpython.com/pypi/micropython-ssd1306/download 官方下载站&#xff1a;https://pypi.org/project/micropython-ssd1306/ 汉字取模说明 取模工具&#xff1a;pctolcd2002取模方式&#xff1a; UTF-8字…
阅读更多...
电路笔记 :芯片封装、电阻电容封装类型介绍

电路笔记 :芯片封装、电阻电容封装类型介绍

芯片的零件型号、位号和封装 项目定义作用零件型号每个零件在设计和制造中的唯一标识符号用于识别零件的特定规格、制造商和其他重要信息位号在电路图或设计图纸上标识每个零件位置的符号帮助准确定位每个零件的位置&#xff0c;以便正确安装到相应位置上封装电子元器件的外部…
阅读更多...
[C++基础学习-06]----C++指针详解

[C++基础学习-06]----C++指针详解

前言 指针是一个存储变量地址的变量&#xff0c;可以用来访问内存中的数据。在C中&#xff0c;指针是一种非常有用的数据类型&#xff0c;可以帮助我们在程序中对内存进行操作和管理。 正文 01-指针简介 指针的基本概念如下&#xff1a; 声明指针&#xff1a;使用“*”符…
阅读更多...
javaweb学习week7

javaweb学习week7

javaweb学习 十四.Springboot 1.配置优先级 Springboot中支持三种格式的配置文件&#xff1a; 注意&#xff1a;虽然Springboot支持多种格式配置文件&#xff0c;但是在项目开发时&#xff0c;推荐使用一种格式的配置&#xff08;yml是主流&#xff09; Springboot除了支持…
阅读更多...
Java的java.util.concurrent.ExecutorService简介

Java的java.util.concurrent.ExecutorService简介

在Java并发编程的璀璨星空中&#xff0c;ExecutorService无疑是那颗最耀眼的明星。它不仅是Java并发编程的核心组件之一&#xff0c;更是构建高并发、高性能应用的秘密武器。今天&#xff0c;我们就来一场说走就走的探索之旅&#xff0c;揭开它的神秘面纱&#xff01; &#x1…
阅读更多...
spring ioc 容器加载过程 refresh() 方法详解

spring ioc 容器加载过程 refresh() 方法详解

IOC 加载过程 从 new ClassPathXmlApplicationContext开始 ApplicationContext context new ClassPathXmlApplicationContext("classpath:application.xml");ClassPathXmlApplicationContext类构造方法 public ClassPathXmlApplicationContext(String[] configLo…
阅读更多...
知识图谱在提升大语言模型性能中的应用：减少幻觉与增强推理的综述

知识图谱在提升大语言模型性能中的应用：减少幻觉与增强推理的综述

幻觉现象指的是模型在生成文本时可能会产生一些听起来合理但实际上并不准确或相关的输出&#xff0c;这主要是由于模型在训练数据中存在知识盲区所致。 为了解决这一问题&#xff0c;研究人员采取了多种策略&#xff0c;其中包括利用知识图谱作为外部信息源。知识图谱通过将信息…
阅读更多...
电子取证平航杯的复现

电子取证平航杯的复现

闻早起部分&#xff1a; 一、闻早起的windows10电脑 &#xff08;1&#xff09;.“闻早起”所使用的笔记本电脑使用何种加密程式&#xff1f; 1.在EFI文件中找到加密程式 &#xff08;2&#xff09; 教徒“闻早起”所使用的笔记本电脑中安装了一款还原软件&#xff0c;其版本…
阅读更多...
测试人员必用的10个Chrome扩展插件

测试人员必用的10个Chrome扩展插件

背景&#xff1a;谷歌Chrome浏览器是全球所有测试人员最受欢迎和必备的浏览器之一&#xff0c;Chrome浏览器为我们提供了许多扩展的选择&#xff0c;可以让我们高效和省时地完成工作。以下为作者观点&#xff1a; 1. Testsigma Recorder Testsigma Recorder用于记录与网络应用…
阅读更多...
嵌入式Linux学习第二天

嵌入式Linux学习第二天

今天学习linuxC编程。首先要熟悉linux下编写c程序的过程。 编写程序Hello World! 首先创建存放程序的文件夹&#xff0c;如下图所示&#xff1a; 接下来在创建一个文件夹来保存这节要编写的代码。指令&#xff1a;mkdir 3.1 接下来我们要设置VIM编辑器的一些配置&#xff0…
阅读更多...
【简单介绍下Debian常用命令】

【简单介绍下Debian常用命令】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…
阅读更多...
AI部署指南

AI部署指南

部署指南 建议大家尽可能的自己去部署&#xff0c;如果实在懒得搞&#xff0c;可以找我来帮你部署&#xff0c;详情参考 服务器代部署说明。 由于时间仓促&#xff0c;文档可能尚未详尽&#xff0c;我将在后续逐步补充详细的说明文档。 架构草图 项目依赖 必选依赖 MySQ…
阅读更多...
DS二叉搜索树

DS二叉搜索树

前言 我们在数据结构初阶专栏已经对二叉树进行了介绍并用C语言做了实现&#xff0c;但是当时没有对二叉搜树进行介绍&#xff0c;而是把他放到数据结构进阶构专栏的第一期来介绍&#xff0c;原因是后面的map和set&#xff08;红黑树&#xff09;是基于搜索树的&#xff0c;这里…
阅读更多...
Java-（乘法表之后）增强for循环

Java-（乘法表之后）增强for循环

这里我们先做个了解&#xff0c;之后我会在数组中进行详细介绍Java5引入了一种主要用于数组或集合的增强型for循环Java增强型for循环语法格式如下 For(声明语句&#xff1a;表达式&#xff09;{ //代码语句 } 声明语句&#xff1a;声明新的局部变量&#xff0c;该变量的类型…
阅读更多...
Windows中安装的PostgreSQL 数据库如何重启

Windows中安装的PostgreSQL 数据库如何重启

1. 使用Windows服务管理器 打开“运行”对话框&#xff08;按WinR键&#xff09;。输入services.msc并按回车&#xff0c;这将打开服务列表。在服务列表中找到PostgreSQL服务。它通常命名为“PostgreSQL”后面跟着版本号和实例名称&#xff0c;例如“PostgreSQL 13 - mydb”。…
阅读更多...
【云原生】Pod 的生命周期（一）

【云原生】Pod 的生命周期（一）

【云原生】Pod 的生命周期&#xff08;一&#xff09;【云原生】Pod 的生命周期&#xff08;二&#xff09; Pod 的生命周期&#xff08;一&#xff09; 1.Pod 生命期2.Pod 阶段3.容器状态3.1 Waiting &#xff08;等待&#xff09;3.2 Running&#xff08;运行中&#xff09;3…
阅读更多...
后缀表达式

后缀表达式

什么是后缀表达式&#xff1f; 在计算机科学和数学领域&#xff0c;表达式求值是一项基本且频繁的任务。我们熟知的中缀表达式&#xff08;如 7 15 ∗ 1 4 ∗ 1&#xff09;直观易读&#xff0c;但在计算机处理时却需要复杂的栈或递归算法来解析。相比之下&#xff0c;后缀表…
阅读更多...
深度学习中的优化算法：选择现有的还是自创？

深度学习中的优化算法：选择现有的还是自创？

深度学习中的优化算法 深度学习中的优化算法&#xff1a;选择现有的还是自创&#xff1f;现有优化算法的优势**优点包括**&#xff1a; 开发新的优化算法的考虑**开发新算法的原因**&#xff1a;**开发新算法的风险**&#xff1a; 实用建议结论 深度学习中的优化算法&#xff1…
阅读更多...
最新文章

Copyright @ 2022~2023