希尔排序算法

1、基本思想

        希尔排序也称缩小增量排序,是插入排序的一种更高效的改进版本。它的基本思想是先将待排序的数组元素按照一定的间隔(称为增量)分成若干个子序列,分别对这些子序列进行插入排序,随着迭代的进行,逐渐减小这个间隔,直到最后间隔为1时,对整个数组进行一次插入排序。通过这种方式,让元素能够在相对较远的位置上快速移动到大致合适的位置,使得后续在间隔较小的插入排序时,元素的移动次数减少,从而提高排序效率。

2、算法步骤

2.1、算法步骤描述:

        1.根据实际情况选择增量序列,增量序列的形式为h1,h2,h3……hn,序列满足h1>h2>h3>……>hn=1,通常h1=N/2,N为待排序数组的长度,常见的增量选取可以按照hi+1=hi/2,也可以按照实际进行其他选择。

        2.根据当前增量将待排序数组分成若干个子序列,每个子序列同等位置的间隔为hi 。例:以数组a[10]={a0,a1,a2,a3,a4,a5,a6,a7,a8,a9},以h1=N/2,hi+1=hi/2进行增量选取,那么第一轮划分中,增量为5,数组arr将被分成如下两个子序列:{a[0],a[5]},{a[1],a[6]},{a[2],a[7]},{a[3],a[8]},{a[4],a[9]}。第二轮划分中,增量为2,数组arr将被分成如下序列:{a[0],a[2],a[4],a[6],a[8]},{a[1],a[3],a[5],a[7],a[9]},增量为1时进行最后一次划分……

        3、对于步骤2中每一轮划分得到的子序列,每个子序列分别进行插入排序。插入排序的过程就是在子序列中,将每个元素与其前面已排好序的元素依次比较并移动到合适位置,使得子序列有序。

        4、当增量减小到1时,对整个数组进行最后一次插入排序,此时数组就完成了排序。

2.2、希尔排序算法动态演示图:

3、代码实现

c语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
void sort(int arr[])
{int gap = N;while(gap != 1){gap = gap/2; //确定本轮排序增量for(int i = 0; i < gap; i++)//增量决定这一轮进行插入排序的次数{for(int j = i; j + gap < N ;j = j + gap)//对根据增量分成的其中一组进行插入排序{int end = j;//重置本轮扫描位置int insert = arr[end+gap];//本轮要插入的数据while(insert < arr[end] && end >= i){arr[end+gap] = arr[end];//移动end = end - gap;//改变下次开始扫描位置}arr[end+gap] = insert;//插入}}}}
int main(int argc, char *argv[])
{srand(time(NULL));int a[N];int i;puts("排序前数组为:");for(i = 0; i < N; i++){a[i] = rand()%100;//为数组随机赋值printf("%d ",a[i]);//输出排序之前数组值}puts("");sort(a);//排序puts("排序后的数组为:");for(i = 0; i < N; i++){printf("%d ",a[i]);//输出排序之后的数组值}puts("");return 0;
}

4、时间复杂度和空间复杂度

希尔排序的时间复杂度与所选择的增量序列密切相关。

平均时间复杂度:O(n^1.3)到O(n^1.5)之间,具体取决于增量序列的选择。

空间复杂度:希尔排序是一种原地排序算法,空间复杂度为O(1)。

稳定性:希尔排序是不稳定的排序算法。在排序过程中,由于相同元素可能在不同的子序列中移动,并且在最后一次整体插入排序时,它们的相对顺序可能会发生改变。

5、适用情况

1、当数据规模不是特别大,且对空间复杂度有一定要求的情况下。

2、由于其实现相对简单,在一些对排序速度要求不是极高、且数据的分布情况不太明确的场景下,也可以考虑使用希尔排序。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

太速科技-634-基于3U PXIe的VU3P FMC+数据接口板

基于3U PXIe的VU3P FMC数据接口板 一、产品概述 板卡是一款基于 3U PXIE 总线架构的高性能数据预处理FMC 载板&#xff0c;具有 1 个 FMC&#xff08;HPC&#xff09;接口&#xff0c;1 个 X8 GTH 背板互联接口&#xff0c;可以实现 1 路 PCIe x8。板卡主控芯片采用Xilin…

OpenCV基本操作(python开发)——(8)实现芯片瑕疵检测

OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;1&#xff09; 读取图像、保存图像 OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;2&#xff09;图像色彩操作 OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;3&…

MySQL数据库中的视图

视图 ​ 本篇将开始介绍有关数据库中视图的相关知识点&#xff0c;其中主要包含视图的基本使用&#xff0c;视图规则和限制。 ​ 视图是一个虚拟表&#xff0c;其内容由查询定义。同真实的表一样&#xff0c;视图包含一系列带有名称的列和行数据&#xff0c;视图的数据变化会…

Docker 镜像拉不动?自建 Docker Hub 加速站 解决镜像拉取失败

本文首发于只抄博客&#xff0c;欢迎点击原文链接了解更多内容。 前言 众所周知&#xff0c;6 月份的时候&#xff0c;Docker Hub 的镜像就已经无法正常拉取&#xff0c;那会随手用 Nginx 反代了一下 Docker Hub&#xff0c;建了个自用的镜像站&#xff0c;一直用到了 9 月份&…

应对传统能源企业管理人员青黄不接问题:搭建系统完善的招聘管理体系

应对传统能源企业管理人员青黄不接问题&#xff1a;搭建系统完善的招聘管理体系 对于很多传统能源企业由于成立时间久&#xff0c;发展到现在&#xff0c;往往都面临着一个共性问题&#xff0c;即未来三到五年&#xff0c;老员工退休后&#xff0c;新员工如何接续的问题。这个…

C++进阶-->红黑树的实现

1、红黑树的概念 红黑树是一棵二叉搜索树&#xff0c;他和前面AVL树不同的是红黑树不是通过平衡因子来保证树的平衡&#xff0c;而是在树结点的处加多了个记录颜色的变量&#xff0c;这个变量可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束&…

Linux操作系统开机引导

linux操作系统的开机引导的过程 linux操作系统开机流程图 1、开机自检&#xff1a;根据bios的设置&#xff0c;对cpu、内存、显卡、键盘等设备进行初步检测&#xff0c;如果以上检测设备正常工作&#xff0c;系统会把控制权移交到硬盘 总结&#xff1a;检测包含系统启动操作系…

DataX 的安装配置和使用 (详细版)

1&#xff0c;上传解压 1&#xff0c;开始上传安装包到你虚拟机上放置安装包的文件夹 2&#xff0c;开始解压 ,配置环境变量 1、上传 /opt/modules 2、解压 tar -zxvf datax.tar.gz -C /opt/installs 3、修改 vi /etc/profile 配置环境变量&#xff1a; export DAT…

蓝桥杯第21场小白入门赛补题

5.蓝桥派对 思路 &#xff1a;一个区间与多少个其他区间有关联&#xff0c;先对所有区间左端点和右端点从小到大排序&#xff0c;对于每个询问&#xff0c;我们先算出[1,r]这个区间里有多少个区间的起点即区间总数&#xff0c;使用upper_bound函数&#xff0c;然后使用lower_bo…

Linux篇(常见入门命令)

目录 一、开启终端 二、Linux命令格式 1. 什么是Linux 的命令&#xff1f; 三、Linux下的命令补全 四、切换用户 五、uname&#xff1a;查看操作系统信息 六、ls&#xff1a;查看目录下文件 1. 用法一 2. 用法二 3. 用法三 七、pwd&#xff1a;显示当前路径 八、cd&…

7.qsqlquerymodel 与 qtableview使用

目录 qtableview 委托QStyledItemDelegateQAbstractItemDelegateCheckBoxItemDelegate使用 qtableview 委托 //设置单元格委托 void setItemDelegate(QAbstractItemDelegate *delegate); QAbstractItemDelegate *itemDelegate() const;//设置列委托 void setItemDelegateForCol…

AMD显卡低负载看视频掉驱动(chrome edge浏览器) 高负载玩游戏却稳定 解决方法——关闭MPO

2024.11.6更新 关闭MPO有点用但是还是驱动掉到恶心&#xff0c;找到终极方法了视频输出直接插主板走核显&#xff0c;稳得一笔&#xff0c;3dmark跑了个分几乎没变化。核显负责桌面浏览器&#xff0c;独显就专心只跑游戏。等24.11驱动再看看 问题 折磨的开始是天下苦黄狗久矣&…

VS2022远程连接调试编译Linux环境下的C++代码

工具&#xff1a;VS2022 虚拟机&#xff1a;RHEL 8.0 一、下载必要工具 1.VS2022组件安装 打开VS2022Installer&#xff0c;点击修改下载必要工具。 选择Linux 和嵌入式开发&#xff0c;然后点击右下角的修改&#xff01; 等待安装........ 安装完成后&#xff0c;创建Linu…

AI笔筒操作说明及应用场景

AI笔筒由来&#xff1a; 在快节奏的现代办公环境中&#xff0c;我们一直在寻找既能提升效率、增添便利&#xff0c;又能融入企业文化、展现个人品味的桌面伙伴。为此&#xff0c;我们特推出专为追求卓越、注重细节的您设计的AI笔筒礼品版&#xff0c;它集高科技与实用性于一身…

爱普生 SG–WriterⅡ 石英可编程手工烧录器

在电子制造与研发的复杂世界中&#xff0c;爱普生 SG–WriterⅡ 石英可编程手工烧录器犹如一把神奇的钥匙&#xff0c;开启了石英晶振编程的无限可能&#xff0c;为众多领域的电子设备注入了精准与稳定的灵魂。 作为手工烧录器&#xff0c;SG–WriterⅡ 独具特色。在当今多样化…

数据库->索引

目录 一、索引是什么 二、索引的数据结构 1.HASH 2.二叉搜索树 3.N叉树(B树) 4.B树 5.B树与B树的区别 三、MYSQL的页 1.页文件头与页文件尾 2.页主体 3.页目录 4.数据页头 四、B在MYSQL索引中的应用 1.应用 2.计算三层树⾼的B树可以存放多少条记录 五、索引分类…

mongodb 按条件进行备份和恢复

在宝塔面板环境下&#xff0c;可以在定时任务设置备份mongodb但是存在缺陷&#xff0c;mongodb如果存储日志&#xff0c;一定时间后会特别巨大&#xff0c;全量备份会导致服务器卡死并很快耗尽磁盘空间&#xff0c;按一定的条件对进行&#xff0c;按天备份数据是必须的。我们用…

从SRE视角透视DevOps的构建精髓

SRE 侧重系统稳定性&#xff0c;DevOps 强调开发运维协作。SRE 实践助力DevOps&#xff0c;提升系统稳定性与团队协作效率。 SRE 运用软件工程的原理&#xff0c;将系统管理员的手工任务自动化&#xff0c;负责运维由系统组件构成的服务&#xff0c;确保服务稳定运行。SRE职责涵…

【数据库】elasticsearch

1、架构 es会为每个索引创建一定数量的主分片和副本分片。 分片&#xff08;Shard&#xff09;&#xff1a; 将索引数据分割成多个部分&#xff0c;每个部分都是一个独立的索引。 主要目的是实现数据的分布式存储和并行处理&#xff0c;从而提高系统的扩展性和性能。 在创建索…

深度学习基础知识-编解码结构理论超详细讲解

编解码结构&#xff08;Encoder-Decoder&#xff09;是一种应用广泛且高效的神经网络架构&#xff0c;最早用于序列到序列&#xff08;Seq2Seq&#xff09;任务&#xff0c;如机器翻译、图像生成、文本生成等。随着深度学习的发展&#xff0c;编解码结构不断演变出多种模型变体…