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

相当于,我们打牌如上图时,我们一般都会使用直接插入排序的方法。
即:在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、在数据-》新建查询-》从其他源-》自网站 ,如图 …...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
