插入排序和希尔排序
目录
- 1.直接插入排序
- 2.希尔排序
1.直接插入排序
基本思想:
把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中,直到所有的数据插入完成为止。
当插入第
i
个元素时,前面的a[0],a[1],...,a[i-1]个数据
已经排好序了,此时用a[i]
与a[i-1],a[i-2],...
进行比较
,找到插入位置就将a[i]插入,原来位置上的元素顺序后移
void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;//记录已经有序的数据的最后一个数据的下标int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else//a[end]<tmp,说明前(i+1)个数已经有序了{break;}}a[end + 1] = tmp;}
}
元素集合月接近有序,直接插入排序算法的时间效率更高
时间复杂度:O(N^2)
稳定性:稳定
2.希尔排序
希尔排序是直接插入排序的优化
1.预排序
2.直接插入排序
基本思想:
先选定一个整数,把待排序文件中所有数据分成gap个组,所有距离为gap的数据分在同一个组里,并对每一组的数据进行排序。然后,取gap=gap/3+1,重复上述分组的操作。当gap=1时,所有数据在同一组的已经排好序了
void ShellSort(int* a, int n)
{int gap = n;while(gap > 1){//+1保证最后一个gap一定是1//gap》1是预排序//gap==1是插入排序gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
当gap>1时都是预排序,目的是让数组更接近有序。当gap==1时,数组已经接近有序了,这样就会很快
时间复杂度:O(N^1.3)(ps:时间复杂度是不固定的)
稳定性:不稳定
相关文章:

插入排序和希尔排序
目录 1.直接插入排序2.希尔排序 1.直接插入排序 基本思想: 把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中,直到所有的数据插入完成为止。 当插入第i个元素时,前面的a[0],a[1],...,a[i-1]个数据已经排好序了,此时用…...

Java web应用性能分析之【java进程问题分析定位】
Java web应用性能分析之【java进程问题分析概叙】-CSDN博客 Java web应用性能分析之【java进程问题分析工具】-CSDN博客 Java web应用性能分析之【jvisualvm远程连接云服务器】-CSDN博客 由于篇幅限制、前面三篇讲了准备工作和分析小结,这里将详细操作java进程问题…...
c#控件笔记
c# PictureBox在工具箱的哪个位置 在 Visual Studio 的工具箱中,PictureBox 控件位于 “Common Controls” 部分。要找到 PictureBox,请按照以下步骤操作: 打开 Visual Studio 并加载您的项目。确保已经打开了设计器视图(即您的…...

STM32-15-DMA
STM32-01-认识单片机 STM32-02-基础知识 STM32-03-HAL库 STM32-04-时钟树 STM32-05-SYSTEM文件夹 STM32-06-GPIO STM32-07-外部中断 STM32-08-串口 STM32-09-IWDG和WWDG STM32-10-定时器 STM32-11-电容触摸按键 STM32-12-OLED模块 STM32-13-MPU STM32-14-FSMC_LCD 文章目录 STM…...

Go语言 几种常见的IO模型用法 和 netpoll与原生GoNet对比
【go基础】16.I/O模型与网络轮询器netpoller_go中的多路io复用模型-CSDN博客 字节开源的netPoll多路复用器源码解析-CSDN博客 一、几种常见的IO模型 1. 阻塞I/O (1) 解释: 用户调用如accept、read等系统调用,向内核发起I/O请求后,应用程序…...

大米cms安装支付逻辑漏洞
1.安装 下载来源:https://www.cnblogs.com/xfbk/p/17910054.html 链接:https://pan.baidu.com/s/1b-Z6RaFBZ6CsSIErY46Pyg?pwdq8qq 提取码:q8qq 注意一下配置就可以了:php5.5apachemysql5.0,主要就是数据库版本要注…...

使用 zxing 生成二维码以及条形码
需求背景 前期在做项目的时候,有一个需求是说要生成一张条形码,并且呢将条形码插入到 excel 中去,但是之前一直没有搞过找个条形码或者是二维码,最后是做出来了,这里呢就先看看怎么生成,后面再抽时间来写写…...
发布 jar 包到 maven 中央仓库
目前开发基本都是以maven或者gradle的方式,直接引入依赖包即可,那么该咋那么发布我们自己的jar包到maven仓库,让别人使用呢?本文适用于2024.3之后的步骤 文章目录 账号准备第一步,注册账号第二步,新建命名空间第三步,验证命名空间第四步,创建 push 的账号和密码点击右…...

AI智能体研发之路-模型篇(四):一文入门pytorch开发
博客导读: 《AI—工程篇》 AI智能体研发之路-工程篇(一):Docker助力AI智能体开发提效 AI智能体研发之路-工程篇(二):Dify智能体开发平台一键部署 AI智能体研发之路-工程篇(三&am…...
英语口语中though的用法(even though、as though)
文章目录 英语口语中 "though" 的用法详解1. "Though" 作为转折连词的用法1.1 基本用法示例句子: 1.2 位置灵活性示例句子: 2. "Though" 作为副词的用法2.1 表示对比或转折示例句子: 2.2 强调前述观点示例句子…...

菜刀冰蝎哥斯拉流量通讯特征绕过检测反制感知
1.加密流程 工具名称requestsresponseAntSwordbase64等方式明文冰蝎2.0开启Openssl扩展-动态密钥aes加密aes加密base64未开启Openssl扩展-异或异或base64冰蝎3.0开启Openssl扩展-静态密钥aes加密aes加密base64未开启Openssl扩展-异或异或base64哥斯拉php的为base64异或base64异…...
前端 JS 经典:判断数组的准确方法
前言:判断数组的方法有很多,但是最完美的只有一个。 1. Object.prototype.toString.call 通过 toString.call 方法来判断是否数组。 function isArray(obj) {return Object.prototype.toString.call(obj) "[object Array]"; } 缺点&#…...
【仓库设置问题】
问题: 某公司在高速公路一些服务站内开设了百货超市,为了能及时给这些百货超市提供足够的商品,他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务,以满足各个超市对商品的需求。现已知这些百货超市在高…...

深度学习知识与心得
目录 深度学习简介 传统机器学习 深度学习发展 感知机 前馈神经网络 前馈神经网络(BP网络) 深度学习框架讲解 深度学习框架 TensorFlow 一个简单的线性函数拟合过程 卷积神经网络CNN(计算机视觉) 自然语言处理NLP Wo…...
Qt for Android
文章 USB Qt for android 获取USB设备列表(一)Java方式 获取 Qt for android 获取USB设备列表(二)JNI方式 获取 Qt for android 串口库使用 Qt for android : libusb在android中使用 Qt for Android : 使用libusb做CH340x串口传…...
HTTP 的三次握手
HTTP 的三次握手是指在建立 TCP 连接时,客户端和服务器之间进行的三步握手过程。这个过程确保了双方都能够互相通信,并且同步了彼此的序列号和确认号。 概念: 第一次握手:客户端发送一个 SYN(同步…...

【Text2SQL 论文】T5-SR:使用 T5 生成中间表示来得到 SQL
论文:T5-SR: A Unified Seq-to-Seq Decoding Strategy for Semantic Parsing ⭐⭐⭐ 北大 & 中科大,arXiv:2306.08368 文章目录 一、论文速读二、中间表示:SSQL三、Score Re-estimator四、总结 一、论文速读 本文设计了一个 NL 和 SQL 的…...
【HarmonyOS】应用屏蔽截屏和录屏
【HarmonyOS】应用屏蔽截屏和录屏 一、问题背景: 金融类或者高密性质的应用APP,对于截屏和录屏场景,某些业务下是禁止不允许。 目前这种场景的需求也是非常有必要的,很多电诈都是通过远程录屏软件,获取到账户密码或者…...
[BUG历险记] ERROR: [SIM 211-100] CSim failed with errors
问题重现 在开发HLS过程中,我碰到一个奇怪的现象,同样的工程,在我重装完系统后,不能进行C仿真了,但是综合实现都是可以正常运作的。 vitis的报错也非常奇怪,单单一行: ERROR: [SIM 211-100] C…...

Redis中大Key与热Key的解决方案
原文地址:https://mp.weixin.qq.com/s/13p2VCmqC4oc85h37YoBcg 在工作中Redis已经成为必备的一款高性能的缓存数据库,但是在实际的使用过程中,我们常常会遇到两个常见的问题,也就是文章标题所说的大 key与热 key。 一、定义 1.1…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...