[导读]希尔排序和插入排序很相似,有点像插入排序的升级版本。希尔排序是希尔(DonaldShell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。希尔排序也是一种插...
希尔排序和插入排序很相似,有点像插入排序的升级版本。
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。
希尔排序也是一种插入排序算法,只不过在插入排序上突破了结界,达到了另一种顶峰的存在,这种顶峰使得时间复杂度变成「O(nLogn)~O(n^2)」。
假设,我们需要给下面的数据进行排序:
结合之前的文章,我们知道两个数据的插入排序就是比较两个数据的大小,然后进行排列。
希尔排序是通过分组 插入。
首先,我们排序的数量是8个,我们需要把数据分成8/2=4组,如下图所示:
对上面4组的数据进行插入排序后得到:
然后,再继续分组8➗2➗2=2分成2组:
这两组数据再进行插入排序,如下图所示:
这样之后,整个数据的排序就差不多完成了。
我们在这个基础上再对整个队列执行一次插入排序,就会完成了整个队列的排序,因为之前已经对数据进行过排序,再进行插入排序的时候,效率会明显得到提升。
整个过程可以观看动态图片:
代码实现看看:
#include
#include
#include
int shell_sort(int arr[],int n)
{
register int i, j, tmp;
int step;
for(step = n/2; step > 0;step /= 2)/*增量步长*/
{
/*step = 4 2 1*/
for(i = step; i < n; i )
{
tmp = arr[i];
j = i - step;
for(;j >= 0
扫描二维码,关注更多精彩内容
本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
ABB变频器是工业自动化领域中广泛应用的电能控制设备,通过改变交流电机供电电源频率和电压来实现对电动机转速的精确调节。本文将详细阐述ABB变频器的基本结构、工作原理以及在不同应用场景中的关键技术。
关键字:
abb
变频器
华盛顿2021年11月24日 /美通社/ -- Afiniti Ltd.(简称“Afiniti”)董事会任命Larry Babbio担任Afiniti董事会主席并立即生效。Babbio先生 自2016年以来一直...
关键字:
ni
abb
(全球TMT2021年11月24日讯)Afiniti Ltd.(简称“Afiniti”)董事会任命Larry Babbio担任Afiniti董事会主席并立即生效。Babbio自2016年以来一直担任Afiniti董事会...
关键字:
Verizon
ni
abb
监控系统俗称「第三只眼」,几乎是我们每天都会打交道的系统,俗话说:无监控、不运维,监控系统的地位不言而喻。先来认识下主流的开源监控系统,Zabbix、Open-Falcon、Prometheus等,今天分享的资料包括【Z...
关键字:
监控系统
abb
在开始今天的文章之前,我先来请大家思考几个小问题。问1:我们在查看内核发送数据消耗的CPU时,是应该看sy还是si?问2:为什么你服务器上的/proc/softirqs里NET_RX要比NET_TX大的多的多?问3:发送...
关键字:
3g
abb
adv
Linux的内存管理可谓是学好Linux的必经之路,也是Linux的关键知识点,有人说打通了内存管理的知识,也就打通了Linux的任督二脉,这一点不夸张。有人问网上有很多Linux内存管理的内容,为什么还要看你这一篇,这...
关键字:
abb
我们知道面向对象的三大特性分别是:封装、继承、多态。很多语言例如:C和Java等都是面向对象的编程语言,而我们通常说C是面向过程的语言,那么是否可以用C实现简单的面向对象呢?答案是肯定的!C有一种数据结构叫做结构体(st...
关键字:
abb
临时变量目前遇到的一些产生临时变量的情况:函数实参、函数返回值、隐式类型转换、多余的拷贝。1.函数实参这点应该比较容易理解,函数参数,如果是实参传递的话,函数体里的修改并不会影响调用时传入的参数的值。那么函数体里操作的对...
关键字:
abb
C20新增了两个const相关的关键字,于是当前存在四个相似的关键字:const,constexpr,consteval和constinit。接下来分别来进行讨论。第一,经过const修饰的变量具有只读属性,并且初始化发...
关键字:
5G
abb
本文以ext2文件系统为例来剖析一个真实的文件系统如何查找文件,这对于深入理解文件系统至关重要。1.准备文件系统镜像所用工具:dd、mkfs.ext2、hexdump、dumpe2fs、mount等工具1)制作100k大...
关键字:
abb
bitmap
直奔主题,多个线程,一个共享变量,不断1。如果代码直接这样写,会产生线程安全问题。public class LongAdder { private long count = 0L; public void ad...
关键字:
abb
boolean
当今世界的任何计算机系统,每天都会生成大量的日志或数据。随着系统的发展,将调试数据存储到数据库中是不可行的,因为它们是不可变的,并且只能用于分析和解决故障。所以,大部分公司倾向于将日志存储在文件中,而这些文件通常位于本地...
关键字:
6G
abb
我认真看完这个妹子的故事了,故事有点长,但很真实。一点一滴记录了一个「非科班半路转行」计算机的不容易。有时候在一个公司呆久了,真的不清楚,外面其他公司的人,都在干嘛。以下是正文。前言本人Java开发6年半不到7年的样子。...
关键字:
abb
AI
branch
简介先赘述一下身份认证和用户授权:用户认证(Authentication):系统通过校验用户提供的用户名和密码来验证该用户是否为系统中的合法主体,即是否可以访问该系统;用户授权(Authorization):系统为用户分...
关键字:
abb
artifact
Authentication
从概念上讲,一条消息是一个发送方与一个或多个接收方之间的一次信息交换。自从大型机问世以来,消息交换一直是计算机编程和架构设计的重要组成部分。多年来,消息传输的实践已经发展成多种消息传输模式。在本文中,我将分享一些较为常用...
关键字:
abb
AC
adca
从数学产生之日起,人们便不断寻求能辅助和加速计算的工具,最终计算工具经历了从简单到复杂、从低级到高级的许多个阶段,演化成了今天的计算机。如今,计算机早已成为我们日常办公和生活中不可或缺的一部分,你对它的前世今生了解多少?...
关键字:
abb
AC
关注「嵌入式大杂烩」,星标公众号,一起进步!来源:嵌入式Linux系统开发Linux上可用的C编译器是GNUC编译器,它建立在自由软件基金会的编程许可证的基础上,因此可以自由发布。GNUC对标准C进行一系列扩展,以增强标...
关键字:
abb
大家好,我是大尧。1.为什么你们公司选择RabbitMQ作为消息中间件在消息队列选型时,我们调研了市场上比较常用ActiveMQ,RabbitMQ,RocketMQ,Kafka。RabbitMQ相对成熟稳定,这是我们选择...
关键字:
abb
前几天粉丝群里有个小伙伴问过:web 页面的未读消息(小红点)怎么实现比较简单,刚好本周手头有类似的开发任务,索性就整理出来供小伙伴们参考,没准哪天就能用得上呢。 之前在 《springboot + rabbitmq 做...
关键字:
abb
在科技界,科学家会给每一个科技术语一个明确的定义,但机器人问世已有几十年,机器人的定义仍然仁者见仁,智者见智,没有一个统一的意见。原因之一是机器人还在发展,新的机型,新的功能不断涌现。根本原
关键字:
abb
发那科
工业机器人
机器人技术
爱普生