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

插入排序与希尔排序

个人主页:Lei宝啊

愿所有美好如期而遇


前言:

这两个排序在思路上有些相似,所以有人觉得插入排序和希尔排序差别不大,事实上,他们之间的差别不小,插入排序只是希尔排序的最后一步。


目录

前言:

插入排序:

思路:

图解:

代码:

希尔排序:

思路:

图解:

代码:


插入排序:

思路:

当我们有了一个有序的数组arr,假设为升序,现在向里面插入一个新数据。

我们假设这个数组有n个元素,最后一个元素的下标我们记作end,那么要插入的这个数下标为end+1,并用tmp记下这个数的大小。

接下来,如果tmp小于arr[end],那么arr[end+1] = arr[end];  end--,

              如果tmp大于等于arr[end],那么break;   arr[end+1] = tmp;  

重复上述操作,直到end < 0或者break跳出


那么面对一个无序的数组,我们可以将第一个元素当做有序,第二个元素为新插入元素,依次类推排序

图解:

代码:

void InsertSort(int* arr, int n)
{//i == n - 2时,temp = arr[n - 1];for (int i = 0; i < n - 1; i++){int end = i;int temp = arr[end + 1];//此处画个图,end小于0跳出循环while (end >= 0){if (temp < arr[end]){//插入的值比end小,end值向后移动一位arr[end + 1] = arr[end];end--;}else{break;}}//写在循环外的原因是如果while循环不是break出来的//会导致第一个元素值重复,插入的值最后未插入进去arr[end + 1] = temp;}}

希尔排序:

思路:

希尔排序比插入排序多的就是预排序,而预排序的目的就是让大的数据/小的数据更快的被排到后面去,因为越接近有序的数据,使用插入排序时时间复杂度越接近O(N),而我们的希尔排序最后一步等同于插入排序

图解:

以代码一为例:

代码:

两个代码没有什么差别,只是一个是一组一组排,一个是并排。

代码一:
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//多组预排序,最后接近有序时插入排序gap /= 2;//完成一趟预排序for (int j = 0; j < gap; j++){//完成一组预排序for (int i = j; i < n - gap; i += gap){//走一组中的一个位置的预排序int end = i;int temp = arr[end + gap];while (end >= 0){if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;}}}}
代码二:
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//多组预排序,最后接近有序时插入排序gap /= 2;//等同于上面的希尔排序,不是分组排了,而是并排for (int i = 0; i < n - gap; i++){//走一组中的一个位置的预排序int end = i;int temp = arr[end + gap];while (end >= 0){if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;}	}
}

相关文章:

插入排序与希尔排序

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 前言&#xff1a; 这两个排序在思路上有些相似&#xff0c;所以有人觉得插入排序和希尔排序差别不大&#xff0c;事实上&#xff0c;他们之间的差别不小&#xff0c;插入排序只是希尔排序的最后一步。 目录 前言&#xff1a;…...

C# OpenCvSharp 基于直线检测的文本图像倾斜校正

效果 项目 代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using OpenCvSharp;namespace OpenCvSharp_基于直线检测的文…...

“智慧时代的引领者:探索人工智能的无限可能性“

目录 一.背景 二.应用 2.1金融领域 2.2医疗领域 2.3教育领域 三.发展 四.总结: 一.背景 人工智能&#xff08;Artificial Intelligence&#xff0c;简称AI&#xff09;&#xff0c;是指通过计算机程序模拟人类智能的一种技术。它是计算机科学、工程学、语言学、哲学等多…...

PMSM——转子位置估算基于QPLL

文章目录 前言仿真模型观测器速度观测位置观测转矩波形电流波形 前言 今后是电机控制方向的研究生的啦&#xff0c;期待有同行互相交流。 仿真模型 观测器 速度观测 位置观测 转矩波形 电流波形...

Android Studio之Gradle和Gradle插件的区别

解释的很详细 Android Studio之Gradle和Gradle插件的区别...

DataExcel控件读取和保存excel xlsx 格式文件

需要引用NPOI库 https://github.com/dotnetcore/NPOI 调用Read 函数将excel读取到dataexcel控件 调用Save 函数将dataexcel控件文件保存为excel文件 using NPOI.HSSF.UserModel; using NPOI.HSSF.Util; using NPOI.SS.UserModel; using NPOI.SS.Util; using System; using …...

【JavaEE】CAS(Compare And Swap)操作

文章目录 什么是 CASCAS 的应用如何使用 CAS 操作实现自旋锁CAS 的 ABA 问题CAS 相关面试题 什么是 CAS CAS&#xff08;Compare and Swap&#xff09;是一种原子操作&#xff0c;用于在无锁情况下保证数据一致性的问题。它包含三个操作数——内存位置、预期原值及更新值。在执…...

第三章:最新版零基础学习 PYTHON 教程(第三节 - Python 运算符—Python 中的关系运算符)

关系运算符用于比较值。它根据条件返回 True 或 False。这些运算符也称为比较运算符。 操作员描述 句法> 大于:如果左操作数大于右操作数,则为 Truex > y...

【GDB】使用 GDB 自动画红黑树

阅读本文前需要的基础知识 用 python 扩展 gdb python 绘制 graphviz 使用 GDB 画红黑树 前面几节中介绍了 gdb 的 python 扩展&#xff0c;参考 用 python 扩展 gdb 并且 python 有 graphviz 模块&#xff0c;那么可以用 gdb 调用 python&#xff0c;在 python 中使用 grap…...

使用Vue3+elementPlus的Tree组件实现一个拖拽文件夹管理

文章目录 1、前言2、分析3、实现4、踩坑4.1、拖拽辅助线的坑4.2、数据的坑4.3、限制拖拽4.4、样式调整 1、前言 最近在做一个文件夹管理的功能&#xff0c;要实现一个树状的文件夹面板。里面包含两种元素&#xff0c;文件夹以及文件。交互要求如下&#xff1a; 创建、删除&am…...

小谈设计模式(7)—装饰模式

小谈设计模式&#xff08;7&#xff09;—装饰模式 专栏介绍专栏地址专栏介绍 装饰模式装饰模式角色Component&#xff08;抽象组件&#xff09;ConcreteComponent&#xff08;具体组件&#xff09;Decorator&#xff08;抽象装饰器&#xff09;ConcreteDecorator&#xff08;具…...

nginx 多层代理 + k8s ingress 后端服务获取客户真实ip 配置

1.nginx http 七层代理 修改命令空间&#xff1a; namespace: nginx-ingress : configmap&#xff1a;nginx-configuration kubectl get cm nginx-configuration -n ingress-nginx -o yaml添加如上配置 compute-full-forwarded-for: “true” forwarded-for-header: X-Forwa…...

6种最常用的3D点云语义分割AI模型对比

由于增强现实/虚拟现实的发展及其在计算机视觉、自动驾驶和机器人领域的广泛应用&#xff0c;点云学习最近引起了人们的关注。 深度学习已成功用于解决 2D 视觉问题&#xff0c;然而&#xff0c;由于其处理面临独特的挑战&#xff0c;深度学习技术在点云上的使用仍处于起步阶段…...

UG NX二次开发(C#)-获取UI中选择对象的handle值

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、设计一个简单的UI界面3、创建工程项目4、测试结果1、前言 我在哔哩哔哩的视频中看到有人问我如何获取UI选择对象的Handle,本来想把Tag、Taggedobject、Handle三者的关系讲一下,然后看…...

win10,WSL的Ubuntu配python3.7手记

1.装linux 先在windows上安装WSL版本的Ubuntu Windows10系统安装Ubuntu子系统_哔哩哔哩_bilibili &#xff08;WSL2什么的一直没搞清楚&#xff09; 图形界面会出一些问题&#xff0c;注意勾选ccsm出的界面设置 win10安装Ubuntu16.04子系统&#xff0c;并开启桌面环境_win…...

02-Zookeeper实战

上一篇&#xff1a;01-Zookeeper特性与节点数据类型详解 1. zookeeper安装 Step1&#xff1a; 配置JAVA环境&#xff0c;检验环境&#xff1a; java -versionStep2: 下载解压 zookeeper wget https://mirror.bit.edu.cn/apache/zookeeper/zookeeper-3.5.8/apache-zookeepe…...

【C语言深入理解指针(1)】

1.内存和地址 1.1内存 在讲内存和地址之前&#xff0c;我们想有个⽣活中的案例&#xff1a; 假设有⼀栋宿舍楼&#xff0c;把你放在楼⾥&#xff0c;楼上有100个房间&#xff0c;但是房间没有编号&#xff0c;你的⼀个朋友来找你玩&#xff0c;如果想找到你&#xff0c;就得挨…...

模拟实现简单的通讯录

前言&#xff1a;生活中处处都会看到或是用到通讯录&#xff0c;今天我们就通过C语言来简单的模拟实现一下通讯录。 鸡汤&#xff1a;跨越山海&#xff0c;终见曙光&#xff01; 链接:gitee仓库&#xff1a;代码链接 目录 主函数声明部分初始化通讯录实现扩容的函数增加通讯录所…...

rabbitMQ死信队列快速编写记录

文章目录 1.介绍1.1 什么是死信队列1.2 死信队列有什么用 2. 如何编码2.1 架构分析2.2 maven坐标2.3 工具类编写2.4 consumer1编写2.5 consumer2编写2.6 producer编写 3.整合springboot3.1 架构图3.2 maven坐标3.3 构建配置类&#xff0c;创建exchange&#xff0c;queue&#x…...

数位dp,338. 计数问题

338. 计数问题 - AcWing题库 给定两个整数 a 和 b&#xff0c;求 a 和 b 之间的所有数字中 0∼90∼9 的出现次数。 例如&#xff0c;a1024&#xff0c;b1032&#xff0c;则 a 和 b 之间共有 9 个数如下&#xff1a; 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出…...

如何解决git clone http/https仓库失败(403错误)

本来不打算写这篇文章&#xff0c;但是后来又遇到这个问题忘了之前是怎么解决的了。 一般情况下&#xff0c;个人使用 GitHub 等平台时是使用 SSH 协议的&#xff0c;这样不光方便管理可访问用户&#xff0c;也保证了安全性。但是 GitHub 上仓库的 SSH 地址是要登陆才能看到&a…...

华为云云耀云服务器L实例评测 | 实例评测使用之硬件性能评测:华为云云耀云服务器下的硬件运行评测

华为云云耀云服务器L实例评测 &#xff5c; 实例评测使用之硬件性能评测&#xff1a;华为云云耀云服务器下的硬件运行评测 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器是什么华为云云耀…...

Elasticsearch:使用 Elasticsearch 进行语义搜索

在数字时代&#xff0c;搜索引擎在通过浏览互联网上的大量可用信息来检索数据方面发挥着重要作用。 此方法涉及用户在搜索栏中输入特定术语或短语&#xff0c;期望搜索引擎返回与这些确切关键字匹配的结果。 虽然关键字搜索对于简化信息检索非常有价值&#xff0c;但它也有其局…...

JVM的主要组成及其作用

jvm主要组成部分有: 类加载器、运行时数据区 (内存结构)、执行引擎、本地接口库、垃圾回收机制 Java程序运行的时候&#xff0c;首先会通过类加载器把Java 代码转换成字节码。然后运行时数据区再将字节码加载到内存中&#xff0c;但字节码文件只是JVM 的一套指令集规范&#xf…...

会议AISTATS(Artificial Intelligence and Statistics) Latex模板参考文献引用问题

前言 在看AISTATS2024模板的时候&#xff0c;发现模板里面根本没有教怎么引用&#xff0c;要被气死了。 如下&#xff0c;引用(Cheesman, 1985)的时候&#xff0c;模板是自己手打上去的&#xff1f;而且模板提供的那三个引用&#xff0c;根本也没有Cheesman这个人&#xff0c…...

2023最新外贸建站:WordPress搭建外贸独立站零基础小白保姆级教程

想从零开始建立一个外贸自建站&#xff0c;那么你来对地方了。 如果你还在找外贸建站或者是WordPress建站教程&#xff0c;不妨看看这篇文章&#xff0c;本教程涵盖了2023最新的外贸建站教程&#xff0c;你将学会使用WordPress自建外贸独立站&#xff0c;步骤包括购买域名主机…...

HTTP请求交互基础(基于GPT3.5,持续更新)

HTTP交互基础 目的HTTP定义详解HTTP协议&#xff08;规范&#xff09;1. 主要组成部分1.1 请求行&#xff08;Request Line&#xff09;&#xff1a;包含请求方法、请求URI&#xff08;Uniform Resource Identifier&#xff09;和HTTP协议版本。1.2 请求头部&#xff08;Reques…...

小谈设计模式(6)—依赖倒转原则

小谈设计模式&#xff08;6&#xff09;—依赖倒转原则 专栏介绍专栏地址专栏介绍 依赖倒转原则核心思想关键点分析abc 优缺点分析优点降低模块间的耦合度提高代码的可扩展性便于进行单元测试 缺点增加代码的复杂性需要额外的设计和开发工作 Java代码实现示例分析 总结 专栏介绍…...

JetBrains常用插件

Codota AI Autocomplete Java and JavaScript&#xff1a;自动补全插件 Background Image plus&#xff1a;背景图片设置 rainbow brackets&#xff1a;彩虹括号&#xff0c;便于识别 CodeGlance2&#xff1a; 类似于 Sublime 中的代码缩略图&#xff08;代码小地图&#xff…...

【C++哈希应用】位图、布隆过滤器

【C哈希应用】位图、布隆过滤器 目录 【C哈希应用】位图、布隆过滤器位图概念位图的实现位图改造位图应用总结布隆过滤器布隆过滤器的提出布隆过滤器的概念布隆过滤器的查找布隆过滤器删除布隆过滤器优点布隆过滤器缺陷 作者&#xff1a;爱写代码的刚子 时间&#xff1a;2023.9…...

毕业设计网站建设/360提交网站收录入口

「2019 Python开发者日」倒计时三天&#xff0c;请扫码咨询 ↑↑↑作者 | 雇个城管打天下&#xff0c;理工男一枚。南京大学软件工程系硕士&#xff0c;一个还在做着拥有十万读者梦的互联网新人&#xff0c;或许一篇文章无法获得你的关注&#xff0c;但突然梦想觉醒的我还在努力…...

如何展示网站操作流程/长尾关键词

编辑&#xff1a;ll ASE65R330-ASEMI高压N沟道MOS管ASE65R330 型号&#xff1a;ASE65R330 品牌&#xff1a;ASEMI 封装&#xff1a;TO-220F 最大漏源电流&#xff1a;12.5A 漏源击穿电压&#xff1a;650V RDS&#xff08;ON&#xff09;Max&#xff1a;0.33mΩ 引脚数量…...

wordpress做第二个/网站收录一键提交

Unclutter for Mac是一款Mac上实用的文件暂存助手&#xff0c;Unclutter类似于 iOS 上的下拉菜单&#xff0c;当我们拖拽一个文件或链接到菜单栏上时&#xff0c;Unclutter会显示出一个暂存空间&#xff0c;让我们把文件或文字放到其中&#xff0c;Unclutter有剪切板、文件存储…...

建设银行官方网站面试详细信息/图片在线转外链

题目链接&#xff1a;http://poj.org/problem?id2524 题目大意&#xff1a;学校共有n个同学&#xff0c;告诉你m对同学信仰同一宗教&#xff0c;问这个学校学生信仰宗教的数目最多为多少。 例&#xff1a; Sample Input 10 91 21 31 41 51 61 71 81 91 1010 42 34 54 85 80 0 …...

网站栏目划分/永久免费自助建站平台

http://codeforces.com/contest/351/problem/E 题意&#xff1a; 给出一些数&#xff0c;可以改变任意数的正负&#xff0c;使序列的逆序对数量最少 因为可以任意加负号&#xff0c;所以可以先把所有数看作正数 序列中的数无论怎么改&#xff0c;都不会改变与绝对值最大的数的逆…...

网站制作软件下载/广州最近爆发什么病毒

右键工程属性 -> 配置属性 -> 生成事件 ->生成后事件&#xff0c;命令行中的路径加上双引号&#xff0c;如 copy $(ProjectDir)\export\win32\Debug\$(ProjectName).dll $(OutDir) 修改为 copy "$(ProjectDir)\export\win32\Debug\$(ProjectName).dll" &quo…...