数据结构-直接插入和希尔排序
这次,我们来讲数据结构的排序的直接插入。
一:排序的思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列

相当于,我们打牌如上图时,我们一般都会使用直接插入排序的方法。
即:在3和9直接插入,对吧。
同样,我们这里的直接排序也是按这种方法来思考。
那么,我们先来上它的动图,来方便我们更清楚。

步骤讲解:(升序)
1.一开始的时候,当第一个的时候,它肯定是有序的,所以我们从第二个数开始插入并比较。
2.先把第二个数用临时变量存起来,再去比较,如果它比前面对比数还要小,就将前面对比数挪到后面,临时变量再去跟更前面的数依次比较。
3.如果临时变量大于对比那个数,就插入到对比数的后面。
4.循环(数据向前插入)进去,直到全部的数都插到正确的位置。
void InsertSort(int* a, int n)
{//整个for (int i = 1; i < n; i++){//单一个int end = i - 1;int temp = a[i];while (end >= 0){if (a[end] > temp) //如果对比数大于存入临时的,就对比数往后挪{a[end + 1] = a[end];end--;}else //如果对比数小于存入临时的,就跳出循环{break;}}a[end + 1] = temp; //在对比数的后面插入数}}
直接插入排序的特性总结:
1. 元素集合越接近有序,直接插入排序算法的时间效率越高
就比如是

你每次插入是都比前面那个数大,那么你是不是就不需要挪动数据了,
假设你有n个数据,按照上面的情况,你执行的次数就是n-1,这样效率是不是就高了。
此时的最好时间复杂度:O(N)。
2.
那么最坏的情况呢?
就是逆序。这样你每次插入的时侯,都是要跟前面的对比数挪动

此时的 时间复杂度:O(N^2)。
3. 空间复杂度:O(1),它是一种稳定的排序算法
4. 稳定性:稳定
优化排序---希尔排序
上面我们已经知道,插入排序的时间复杂度O(N^2).
那么有什么办法使他们的效率更高一点呢?
这里大佬们提出了希尔排序的方法。
思路:
1.用间隔为gap的变量分别对每组数插入
2.预排序:它的目标就是接近有序
3.最后再直接插入
这样的方法会大大提高效率。
比如说,你看:按照下面的话分组

这一趟排序完,是不是就看起来比没有排时变有序了。


这样,一趟趟地回来,到gap==1时,就只需挪隔壁的数字比较,所以大大提高了直接插入的效率。
比较:
我们知道上面直接排序:
直接插入:完全逆序时:

它比较执行的次数(1+2+3……n-1)次
根据等差数列的公式:n^2/2-n/2;
那么,我们使用希尔排序,(用gap分组)
gap=gap/4时

分成两部分:
那么它的次数(1+2+……+n/2-1)+(1+2+……+n/2-1)
那么计算得到:n^2/4-n/2;
相比,你看,是不是就提高了效率。
gap=gap/2

假设为n,则分成3部分
执行的次数:(1+2+3+……n-1)*3
计算得: n^2/6-n/2;
类比得:当我们分的部分越多,执行的次数会减少。
有以下规律:
当分成部分k,执行次数:
1/k*n^2/2-n/2
当gap越小,跳得越慢,越有序,当gap越大,跳得越慢,越无序。
那么我们发现,当gap很小时,它的次数本来是n^2/2-n/2,但是,,我们考虑到之前我们已经经过预排序了,已经很接近有序了,所以按照最好的情况来算。
总结:
希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。
希尔排序的特性总结:
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定
根据大佬们的推算,一般都是gap=(gap/3)+1常用
int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < gap; i++){for (int i = 0; i < n - gap; i += gap){//单个int end = i;int temp = a[i + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}}}
好了,选择排序和希尔排序就写完了。
最后,学路漫漫,永无止境,一点一点进步吧!
相关文章:
数据结构-直接插入和希尔排序
这次,我们来讲数据结构的排序的直接插入。 一:排序的思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 相当于,我们打牌如上图…...
vue3表单验证的时候访问接口如果有值就通过否则不通过.主动去触发校验
页面有个身份证号码的校验。校验完身份证格式是否符合之后还要去访问接口查询这个用户是否存在。如果存在才通过验证。否则就校验不通过 <el-form ref"ruleFormRef" :model"form" label-width"140px" label-position"right" label…...
Trae根据原型设计稿生成微信小程序密码输入框的踩坑记录
一、需求描述 最近经常使用Trae生成一些小组件和功能代码(对Trae赶兴趣的可以看之前的文章《TraeAi上手体验》),刚好在用uniapp开发微信小程序时需要开发一个输入密码的弹框组件,于是想用Trae来实现。原型设计稿如下:…...
【数据结构】 最大最小堆实现优先队列 python
堆的定义 堆(Heap)是一种特殊的完全二叉树结构,通常分为最大堆和最小堆两种类型。 在最大堆中,父节点的值总是大于或等于其子节点的值; 而在最小堆中,父节点的值总是小于或等于其子节点的值。 堆常用于实…...
基于多层感知机(MLP)实现MNIST手写体识别
实现步骤 下载数据集处理好数据集确定好模型(初始化模型参数等等)确定优化函数(损失函数也称为目标函数)和优化方法(一般选用随机梯度下降 SDG )进行模型的训练进行模型的评估 import torch import torch…...
QT和有道词典有冲突,导致内存溢出,闪退。
提示:本文为学习记录,若有疑问,请联系作者。 前言 具体详细查看此博主:原文链接 在使用Qt Designer时,如果开启了有道词典,会导致Qt Designer崩溃。估计应该是把有道词典屏幕取词功能打开后,有…...
4. 示例:创建带约束的随机地址生成器(范围0x1000-0xFFFF)
文章目录 前言代码示例:运行方法:查看结果:关键功能说明:扩展功能建议: 前言 以下是一个完整的SystemVerilog测试平台示例,包含约束随机地址生成、日志输出和波形生成功能: 代码示例࿱…...
VSCode轻松调试运行C#控制台程序
1.背景 我一直都是用VS来开发C#项目的,用的比较顺手,也习惯了。看其他技术文章有介绍VS Code更轻量,更方便。所以我专门花时间来使用VS Code,看看它是如何调试代码、如何运行C#控制台。这篇文章是一个记录的过程。 2.操作 2.1 V…...
内容中台是什么?内容管理平台解析
内容中台的核心价值 现代企业数字化转型进程中,内容中台作为中枢系统,通过构建统一化的内容管理平台实现数据资产的高效整合与智能调度。其核心价值体现在打破传统信息孤岛,将分散于CRM、ERP等系统的文档、知识库、产品资料进行标准化归集&a…...
sqlmap:自动SQL注入和数据库接管工具
SQL 注入攻击是 Web 安全领域最常见的漏洞之一,今天给大家介绍一个自动化 SQL 注入和数据库接管工具:sqlmap。sqlmap 作为一款开源渗透测试工具,能帮助安全测试人员快速发现并利用 SQL 注入漏洞接管数据库服务器。 功能特性 sqlmap 使用 Pyt…...
Python设置阿里云镜像源教程:解决PIP安装依赖包下载速度慢的问题
在 Python 中,你可以通过修改 pip 的配置文件来设置阿里云镜像源,以加速包的安装。以下是具体步骤: 1. 临时使用阿里云镜像源 你可以在使用 pip 安装包时,通过 -i 参数临时指定阿里云镜像源: pip install <packa…...
基于专利合作地址匹配的数据构建区域协同矩阵
文章目录 地区地址提取完成的处理代码 在专利合作申请表中,有多家公司合作申请。在专利权人地址中, 有多个公司的地址信息。故想利用这里多个地址。想用这里的地址来代表区域之间的专利合作情况代表区域之间的协同、协作情况。 下图是专利合作表的一部分…...
Java集合List快速实现重复判断的10种方法深度解析
文章目录 引言:为什么需要关注List重复判断?一、基础实现方法1.1 暴力双循环法1.2 HashSet法 二、进阶实现方案2.1 Stream API实现2.2 TreeSet排序法 三、高性能优化方案3.1 并行流处理3.2 BitSet位图法(仅限整数) 四、第三方库实…...
List的模拟实现(2)
前言 上一节我们讲解了list的基本功能,那么本节我们就结合底层代码来分析list是怎么实现的,那么废话不多说,我们正式进入今天的学习:) List的底层结构 我们先来看一下list的底层基本结构: 这里比较奇怪的…...
如何使用SaltStack批量替换SSL证书方案
以下是借助 SaltStack 批量替换 SSL 证书的完整方案,该方案结合了自动化更新与回滚机制,以保障操作的高效性与安全性: 一、准备工作 目录结构搭建 在 Salt Master 的 /home/salt/ssl_update 目录下构建如下结构:ssl_update/ ├──…...
Golang快速上手01/Golang基础
最近有需求,需要使用go,这几天快速过一遍基础语法,这是今天的总结 项目结构 #mermaid-svg-qpF09pnIik9bqQ4E {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-qpF09pnIik9bqQ4E .e…...
[Web 安全] 反序列化漏洞 - 学习笔记
关注这个专栏的其他相关笔记:[Web 安全] Web 安全攻防 - 学习手册-CSDN博客 0x01:反序列化漏洞 — 漏洞介绍 反序列化漏洞是一种常见的安全漏洞,主要出现在应用程序将 序列化数据 重新转换为对象(即反序列化)的过程中…...
【学习笔记】Google的Lyra项目:基于神经网络的超低比特率语音编解码技术
一、引言:语音通信的带宽挑战与技术突破 在实时音视频通信占据全球数字化生活核心地位的今天,Google于2021年推出的Lyra编解码器标志着语音编码技术进入新的时代。这款基于机器学习的新型音频编解码器以3kbps的极低比特率实现接近原始音质的语音重建能力…...
Unity Dedicated Server 控制台 输出日志LOg 中文 乱码
现象: 中文乱码 原因: Unity打包出来的.exe文件,语言一栏是英文,VS控制台出来不一样 解决方案: 新建.bat文件 ,并使用命令chcp 65001,运行时启动.bat,而不是.exe, 改不了exe属性,虽然有点奇怪ÿ…...
【Excel】 Power Query抓取多页数据导入到Excel
抓取多页数据想必大多数人都会,只要会点编程技项的人都不会是难事儿。那么,如果只是单纯的利用Excel软件,我还真的没弄过。昨天,我就因为这个在网上找了好久发好久。 1、在数据-》新建查询-》从其他源-》自网站 ,如图 …...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
