【C语言】插入排序、希尔排序——动图展示

目录

  • 1. 插入排序
    • 1.1 基本概念
    • 1.2 实现思路
    • 1.3 代码部分
  • 2. 希尔排序
    • 2.1 为什么会有希尔排序?
    • 2.2 基本概念
    • 2.3 实现思想
      • 1)单组排序
      • 2)多组排序
    • 2.4 代码部分
  • 3. 总结


1. 插入排序

1.1 基本概念

待排序的记录逐个插入到一个已经排好序有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

  • 实际中我们玩扑克牌时,梳理牌的过程,就用了插入排序的思想
    在这里插入图片描述

假设n个数,n-1的数已经是排序好的(n>1,因为1个数默认是有序的),把第n个数插入到合适的位置,依次将数据插入到排好序的合适位置,直到所有数据都有序,这样长度为n个数就排好序了。
在这里插入图片描述

1.2 实现思路

思路(以升序为例)

  1. 假设第一个数据(下标0)有序,后面的n-1个数据都需要插入到有序数组里
  2. 保存有序数据后面一个数据(tmp)
  3. 移动数据,需要把新数据插入有序数据中的合适位置(tmp < end)
  4. 移动数据停止条件有两个
  • 最坏情况:tmp比全部有序的数据要小,有序数据从头到尾都需要移动,end移动到-1,说明移动完成。
  • tmp > end下标的数据,说明已经有序了。
  1. 插入数据到end+1的下标位置,因为end下标的数据是小于tmp。

1.3 代码部分

// 插入排序(升序)
void InsertSort(int* a, int n)
{	// i迭代n - 1结束,到n结束会越界,因为需要访问未排序的数据(i+1 == n+1),就会越界for (int i = 0; i < n - 1; i++){int end = i;	// 有序的个数int tmp = a[end + 1];	// 需要插入的新数据(未排序的数据)// 新的数据想要插入都有序数据中,需要移动数据,插入到合适的位置// 以升序为例,最坏情况:新数据比全部有序的数据要小,有序数据都需要移动// while和if条件合并判断如下while (end >= 0 && tmp < a[end]){a[end + 1] = a[end];end--;}while (end >= 0){// 新数据小于有序数据就要移动数据if (tmp < a[end]){a[end + 1] = a[end];end--;}else{// 已经有序break;}}// 插入数据到end+1的下标位置,end < tmpa[end + 1] = tmp;}
}

2. 希尔排序

2.1 为什么会有希尔排序?

直接插入排序有缺陷,就是数据是接近逆序逆序的时候,排的非常慢,效率很低,但是直接插入排序在数据接近有序的情况下,效率很高,而希尔排序就是直接插入排序的优化,他就是能解决数据逆序排的慢问题。

2.2 基本概念

希尔排序法又称缩小增量法,插入排序的优化。希尔排序法的基本思想是:先选定一个整数(gap),把待排所有数据分成gap个组,所有距离为差相同的数据分在同一组内,并对每一组内的记录进行排序。然后缩小gap,重复上述分组和排序的工作。当到达gap=1时,所有数据在统一组内排好序。

在这里插入图片描述
在这里插入图片描述

2.3 实现思想

排序分为两步:

  • 预排序 gap > 1,目的是让数据接近有序
  • 直接排序 gap = 1,目的是数据有序

1)单组排序

假设gap = 3,逆序数组排一组序
在这里插入图片描述

从上图看到,在一组数据中最大值就排到最后的位置

代码演示:

	int gap = 3;for (int end = 0; end < n - gap; end += gap){int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}

这里我们可以发现,单趟排序和直接插入排序,大同小异,只不过把1的位置换成gap。

2)多组排序

多趟排序,相比于单趟,单趟只能排一组为相差gap的数,而多趟可以排多组相差gap的数。

实现起来也很简单,只不过是让end的递增为1(end++),只不过未排序的数据以当前end+gap,就能相差gap,分组数据同时排序了,不过需要注意的是结束条件 end < n - gap,否则会造成越界,因为未数据是保存的是当前end+gap(a[end + gap]),大家可以看下图
在这里插入图片描述

gap为4,逆序数组排多组序
在这里插入图片描述

从结果来看上面的数据不仅没有排成接近有序,反而变得更乱了,但是他排的很快,因为每次递增gap,最终结束条件是n -gap,而且能让大的数越快排到后面

gap为3,逆序数组多趟排一组序

在这里插入图片描述

上图显示一组的多趟排序,相同颜色为一组,可以看到将数据变得接近有序了,我们只需要在缩小gap,数据会越来越有序,直到gap=1,直接插入排序。

所以如:排升序

  • gap越大,大的数越快到后面,小的数越快到前面,但是预排序完,越不接近有序
  • gap越小,序列越接近有序

所以我们可以先让gap很大,再让gap很小,这样排序完,就可以很好的解决逆序问题,同时效率相比直接插入排序,大大提升

希尔排序和插入排序最大区别就是分组排序,不像插入排序每次连续数据比较,差距为1

gap设置多少合适呢?

希尔排序会根据数据的个数来计算出gap,以达到gap就合适的距离。
最好gap是每次 gap / 3gap / 2
gap / 3:时间复杂度 O ( l o g 3 N ) O(log_3N) Olog3N,gap / 3 / 3 / 3 / 3 / …… = 0
gap / 2:时间复杂度 O ( l o g 2 N ) O(log_2N) Olog2N,gap / 2 / 2 / 2 / 2 / …… = 1

注意gap / 3,不能保证最后结果是1,我们需要在运算后+1,如6 / 3 = 2,2 / 3 = 0,0就不能满足我想要的插入排序。

gap / 3,官方总结算出的时间复杂度是 O ( N 1.3 ) O(N^{1.3}) O(N1.3)

2.4 代码部分

这里注释写的并不多,因为大多数地方是和直接插入排序相似,直接插入排序注释写的比较详细

// 希尔排序(升序)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// 缩小gap,最后加1,是确保最后gap=1,为直接插入排序gap = gap / 3 + 1;// 一次排多组差距为gap的数据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];}else{break;}}a[end + gap] = tmp;}}
}

3. 总结

直接插入时间复杂度是 O ( N 2 ) O(N^2) O(N2),比如在排逆序数据的时候,但是在有序或接近有序的时间,效率很高,所以希尔排序就对这个缺陷进行了优化,预排序就可以很好解决的这个问题,希尔排序平均复杂度是 O ( N 1.3 ) O(N^{1.3}) O(N1.3)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/418989.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[数据集][目标检测]电动车头盔佩戴检测数据集VOC+YOLO格式4235张5类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4235 标注数量(xml文件个数)&#xff1a;4235 标注数量(txt文件个数)&#xff1a;4235 标注…

在OpenEuler(欧拉)系统上用kubeadm部署(k8s)Kubernetes集群

一、OpenEuler(欧拉) 系统简介 openEuler 是开放原子开源基金会&#xff08;OpenAtom Foundation&#xff09;孵化及运营的开源项目&#xff1b; openEuler作为一个操作系统发行版平台&#xff0c;每两年推出一个LTS版本。该版本为企业级用户提供一个安全稳定可靠的操作系统。…

[数据集][目标检测]智慧农业草莓叶子病虫害检测数据集VOC+YOLO格式4040张9类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4040 标注数量(xml文件个数)&#xff1a;4040 标注数量(txt文件个数)&#xff1a;4040 标注…

10个好用的AI写作工具【亲测免费】

1. 光速写作 传送入口&#xff1a;http://u3v.cn/6hXWYa AI打工神器&#xff0c;一键生成文章&ppt 2. 讯飞写作 传送入口&#xff1a;http://m6z.cn/5ODiSw 3. 讯飞绘文 传送入口&#xff1a;https://turbodesk.xfyun.cn/?channelidgj3 4. AI排版助手 传送入口&#…

jenkins 安装

jenkins安装 jenkins官网 中文网址 安装设置 所有jenkins版本 内存512M以上&#xff0c;10Gb磁盘&#xff1b;安装jdk&#xff0c;需要java8以上下载较新的版本&#xff0c;否则安装插件时可能报错版本过低 # 搜索java yum search java | grep -iE "jdk"# 安装jd…

网络安全知识科普:什么是网络准入控制系统?有哪些?

在当今数字化时代&#xff0c;网络安全已成为企业和组织不可忽视的重要议题。随着远程工作模式的普及和物联网设备的增加&#xff0c;网络边界越来越模糊&#xff0c;传统防火墙已经不足以应对日益复杂的威胁环境。在这种背景下&#xff0c;网络准入控制系统(Network Access Co…

最多购买宝石数目

题目描述 橱窗里有一排宝石&#xff0c;不同的宝石对应不同的价格&#xff0c;宝石的价格标记为 gems[i] 0≤i<nn gems.length 宝石可同时出售0个或多个&#xff0c;如果同时出售多个&#xff0c;则要求出售的宝石编号连续; 例如客户最大购买宝石个数为m&#xff0c;购买…

Nginx 负载均衡+高可用 集群部署(Keepalived+LVS DR模式)

一、LVS负载均衡简介 1.1 LVS基本介绍 LVS&#xff08;Linux Virtual Server&#xff09;即Linux虚拟服务器&#xff0c;是由章文嵩博士主导开发的开源负载均衡项目&#xff0c;目前LVS已经被集成在Linux内核中。该项目在Linux内核中实现了基于IP地址的请求数据负载均衡调度方…

如何使用正则表达式替换字符串中的特定位置数字

如何使用正则表达式替换字符串中的特定位置数字 1、效果 把字符串中的第一个123替换掉: 2、代码 使用正则中的sub函数: re.sub(pattern,repl,string,count=0,flags=0) pattern:表示需要匹配的模式,即需要被替换的字符或字符串。 repl:表示替换后的字符串或函数,用于…

多目标应用:四种多目标优化算法(NSGA2、NSPSO、NSDBO、NSCOA)求解柔性作业车间调度问题(FJSP),MATLAB代码

一、柔性作业车间调度问题 柔性作业车间调度问题(Flexible Job Scheduling Problem, FJSP) 的描述如下&#xff1a;n个工件 { J , J 2 , . . , J n } \{J,J_2,..,J_n\} {J,J2​,..,Jn​}要在 m m m 台机器 { M 1 , M 2 , . . , M m } \{M_1,M_2,..,M_m\} {M1​,M2​,..,Mm​} …

spring 事物使用场景说明

事务使用场景。 在某些业务场景下&#xff0c;如果一个请求中&#xff0c;需要同时写入多张表的数据。为了保证操作的原子性&#xff08;要么同时成功&#xff0c;要么同时失败&#xff09;&#xff0c;避免数据不一致的情况&#xff0c;我们一般都会用到spring事务。 确实&am…

【Shiro】Shiro 的学习教程(五)之 SpringBoot 集成 Shiro + JWT

与 Spring 集成&#xff1a;与 Spring 集成 与 SpringBoot 集成&#xff1a;与 SpringBoot 集成 1、SpringBoot Shiro Jwt ①&#xff1a;引入 pom.xml&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-…

【网络安全】服务基础第二阶段——第三节:Linux系统管理基础----Linux用户与组管理

目录 一、用户与组管理命令 1.1 用户分类与UID范围 1.2 用户管理命令 1.2.1 useradd 1.2.2 groupadd 1.2.3 usermod 1.2.4 userdel 1.3 组管理命令 1.3.1 groupdel 1.3.2 查看密码文件 /etc/shadow 1.3.4 passwd 1.4 Linux密码暴力破解 二、权限管理 2.1 文件与目…

sping boot 基于 RESTful 风格,模拟增删改查操作

RESTful -> 增&#xff1a;post 删&#xff1a;delete 改: put 查: get RESTful 资源路径&#xff0c;一般以 s 复数结尾 以下是代码示例&#xff1a; package com.example.springboot.controller;import org.springframework.web.bind.annotation.*;RestControll…

Mac+Pycharm配置PyQt6教程

安装包 pip install PyQt6 PyQt6-tools #查看Qt版本 pip show PyQt6 pip show pyqt6-tools 配置扩展工具 QTD(界面设计) Program&#xff1a;/Users/wan/PycharmProjects/NewDemo/venv/lib/python3.11/site-packages/qt6_applications/Qt/bin/Designer.app Working directo…

虚拟机ubuntu配置opencv和opencv_contrib

前期准备 1.下载opencv和opencv_contrib源码 opencv-4.6.0&#xff1a;https://opencv.org/releases/ opencv_contrib-4.6.0&#xff1a;https://github.com/opencv/opencv_contrib 在ubuntu直接下载或者在window上下好传到虚拟机里都可以 自己找个地方把他们解压&#xf…

基于springboot+vue+uniapp的“共享书角”图书借还管理系统小程序

开发语言&#xff1a;Java框架&#xff1a;springbootuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#…

Leetcode69.x的平方根

题目 代码&#xff08;首刷看解析 2024年9月8日&#xff09; 注意相乘越界问题 class Solution { public:int mySqrt(int x) {if (x 0) return 0;if (x 1) return 1;int left 1;int right x / 2;while (left < right) {int mid left (right - left) / 2;if (mid <…

【第0007页 · 数组】数组中重复的数据(如何实现数组的原地修改)

【前言】本文以及之后的一些题解都会陆续整理到目录中&#xff0c;若想了解全部题解整理&#xff0c;请看这里&#xff1a; 第0007页 数组中重复的数据 今天&#xff0c;我们来看一个在实际工作中运用不多&#xff0c;但是对于一些算法题还是有必要的奇技淫巧——数组的原地修…

探索非局部均值滤波在椒盐噪声去除中的应用

在图像处理领域&#xff0c;椒盐噪声是一种常见的干扰&#xff0c;它会导致图像出现随机的黑白像素点&#xff0c;严重影响图像质量。为了解决这一问题&#xff0c;本文将介绍一种有效的去噪技术——非局部均值滤波&#xff08;NLM&#xff09;的改进版本&#xff0c;即NAMF&am…