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

插入排序和希尔排序

目录

  • 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.直接插入排序 基本思想&#xff1a; 把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的数据插入完成为止。 当插入第i个元素时&#xff0c;前面的a[0],a[1],...,a[i-1]个数据已经排好序了&#xff0c;此时用…...

Java web应用性能分析之【java进程问题分析定位】

Java web应用性能分析之【java进程问题分析概叙】-CSDN博客 Java web应用性能分析之【java进程问题分析工具】-CSDN博客 Java web应用性能分析之【jvisualvm远程连接云服务器】-CSDN博客 由于篇幅限制、前面三篇讲了准备工作和分析小结&#xff0c;这里将详细操作java进程问题…...

c#控件笔记

c# PictureBox在工具箱的哪个位置 在 Visual Studio 的工具箱中&#xff0c;PictureBox 控件位于 “Common Controls” 部分。要找到 PictureBox&#xff0c;请按照以下步骤操作&#xff1a; 打开 Visual Studio 并加载您的项目。确保已经打开了设计器视图&#xff08;即您的…...

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) 解释&#xff1a; 用户调用如accept、read等系统调用&#xff0c;向内核发起I/O请求后&#xff0c;应用程序…...

大米cms安装支付逻辑漏洞

1.安装 下载来源&#xff1a;https://www.cnblogs.com/xfbk/p/17910054.html 链接&#xff1a;https://pan.baidu.com/s/1b-Z6RaFBZ6CsSIErY46Pyg?pwdq8qq 提取码&#xff1a;q8qq 注意一下配置就可以了&#xff1a;php5.5apachemysql5.0&#xff0c;主要就是数据库版本要注…...

使用 zxing 生成二维码以及条形码

需求背景 前期在做项目的时候&#xff0c;有一个需求是说要生成一张条形码&#xff0c;并且呢将条形码插入到 excel 中去&#xff0c;但是之前一直没有搞过找个条形码或者是二维码&#xff0c;最后是做出来了&#xff0c;这里呢就先看看怎么生成&#xff0c;后面再抽时间来写写…...

发布 jar 包到 maven 中央仓库

目前开发基本都是以maven或者gradle的方式,直接引入依赖包即可,那么该咋那么发布我们自己的jar包到maven仓库,让别人使用呢?本文适用于2024.3之后的步骤 文章目录 账号准备第一步,注册账号第二步,新建命名空间第三步,验证命名空间第四步,创建 push 的账号和密码点击右…...

AI智能体研发之路-模型篇(四):一文入门pytorch开发

博客导读&#xff1a; 《AI—工程篇》 AI智能体研发之路-工程篇&#xff08;一&#xff09;&#xff1a;Docker助力AI智能体开发提效 AI智能体研发之路-工程篇&#xff08;二&#xff09;&#xff1a;Dify智能体开发平台一键部署 AI智能体研发之路-工程篇&#xff08;三&am…...

英语口语中though的用法(even though、as though)

文章目录 英语口语中 "though" 的用法详解1. "Though" 作为转折连词的用法1.1 基本用法示例句子&#xff1a; 1.2 位置灵活性示例句子&#xff1a; 2. "Though" 作为副词的用法2.1 表示对比或转折示例句子&#xff1a; 2.2 强调前述观点示例句子…...

菜刀冰蝎哥斯拉流量通讯特征绕过检测反制感知

1.加密流程 工具名称requestsresponseAntSwordbase64等方式明文冰蝎2.0开启Openssl扩展-动态密钥aes加密aes加密base64未开启Openssl扩展-异或异或base64冰蝎3.0开启Openssl扩展-静态密钥aes加密aes加密base64未开启Openssl扩展-异或异或base64哥斯拉php的为base64异或base64异…...

前端 JS 经典:判断数组的准确方法

前言&#xff1a;判断数组的方法有很多&#xff0c;但是最完美的只有一个。 1. Object.prototype.toString.call 通过 toString.call 方法来判断是否数组。 function isArray(obj) {return Object.prototype.toString.call(obj) "[object Array]"; } 缺点&#…...

【仓库设置问题】

问题&#xff1a; 某公司在高速公路一些服务站内开设了百货超市&#xff0c;为了能及时给这些百货超市提供足够的商品&#xff0c;他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务&#xff0c;以满足各个超市对商品的需求。现已知这些百货超市在高…...

深度学习知识与心得

目录 深度学习简介 传统机器学习 深度学习发展 感知机 前馈神经网络 前馈神经网络&#xff08;BP网络&#xff09; 深度学习框架讲解 深度学习框架 TensorFlow 一个简单的线性函数拟合过程 卷积神经网络CNN&#xff08;计算机视觉&#xff09; 自然语言处理NLP Wo…...

Qt for Android

文章 USB Qt for android 获取USB设备列表&#xff08;一&#xff09;Java方式 获取 Qt for android 获取USB设备列表&#xff08;二&#xff09;JNI方式 获取 Qt for android 串口库使用 Qt for android : libusb在android中使用 Qt for Android : 使用libusb做CH340x串口传…...

HTTP 的三次握手

​​​​​ HTTP 的三次握手是指在建立 TCP 连接时&#xff0c;客户端和服务器之间进行的三步握手过程。这个过程确保了双方都能够互相通信&#xff0c;并且同步了彼此的序列号和确认号。 概念&#xff1a; 第一次握手&#xff1a;客户端发送一个 SYN&#xff08;同步…...

【Text2SQL 论文】T5-SR:使用 T5 生成中间表示来得到 SQL

论文&#xff1a;T5-SR: A Unified Seq-to-Seq Decoding Strategy for Semantic Parsing ⭐⭐⭐ 北大 & 中科大&#xff0c;arXiv:2306.08368 文章目录 一、论文速读二、中间表示&#xff1a;SSQL三、Score Re-estimator四、总结 一、论文速读 本文设计了一个 NL 和 SQL 的…...

【HarmonyOS】应用屏蔽截屏和录屏

【HarmonyOS】应用屏蔽截屏和录屏 一、问题背景&#xff1a; 金融类或者高密性质的应用APP&#xff0c;对于截屏和录屏场景&#xff0c;某些业务下是禁止不允许。 目前这种场景的需求也是非常有必要的&#xff0c;很多电诈都是通过远程录屏软件&#xff0c;获取到账户密码或者…...

[BUG历险记] ERROR: [SIM 211-100] CSim failed with errors

问题重现 在开发HLS过程中&#xff0c;我碰到一个奇怪的现象&#xff0c;同样的工程&#xff0c;在我重装完系统后&#xff0c;不能进行C仿真了&#xff0c;但是综合实现都是可以正常运作的。 vitis的报错也非常奇怪&#xff0c;单单一行&#xff1a; ERROR: [SIM 211-100] C…...

Redis中大Key与热Key的解决方案

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

手游刚开服就被攻击怎么办?如何防御DDoS?

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

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

Android15默认授权浮窗权限

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

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列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的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...