常见排序算法之插入排序

news/2024/7/22 13:37:59/文章来源:https://blog.csdn.net/paradiso989/article/details/139270064

目录

一、直接插入排序

1.1 什么是插入排序

1.2 代码思路

1.3 C语言源码

二、希尔排序

2.0 插入排序的弊端

2.1 什么是希尔排序?

2.2 排序思路

2.3 C语言源码


一、直接插入排序

1.1 什么是插入排序

插入排序是一种简单直观的排序算法,它通过构建有序序列,对未排序数据逐个插入到合适的位置,从而达到排序的目的。

具体操作为:将第一个元素视为已排序部分,然后依次将后面的元素插入到已排序部分,直到所有元素都插入完成为止。

插入排序的时间复杂度为O(N^2),是一种稳定的排序算法。

1.2 代码思路

采取先部分后整体的思路进行讲解

  • 部分
  1. 假设前n个元素均为已排序好的元素,已排序好的最后一个元素的数组下标为end
  2. 将end+1下标对应的值与end对应的值进行比较
    如果大于前一个值,则在end+1的位置插入该值。
    如果小于前一个值,则在end-1的位置插入该值。
  3. 循环比较已经排序好的元素的值与end+1的值,重复插入操作。
    在比较有限次后若发现满足条件,则跳出循环。
    考虑最坏的情况,如果end-1为0时,也就是插入到了数组的第一个位置,则跳出循环。
  • 整体
  1. 从n=0开始循环,假设循环i次,那么每次已排序好的数组最后一个下标就是数组的大小-i
  2. 关键问题是要进行多少次循环?

1.3 C语言源码

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] > a[end + 1]){a[end + 1] = a[end];end--;}else{break;}a[end + 1] = tmp;}}
}

二、希尔排序

2.0 插入排序的弊端

插入排序的主要弊端在于其时间复杂度较高。在最坏情况下,插入排序的时间复杂度为O(n^2),因此对于大规模数据集合来说,插入排序的效率较低。尤其是当数组是升序排序时,想要转成降序排序,效率极低。

由此衍生出希尔排序。通过引入增量序列,将整个数据集合分成多个子序列,并对每个子序列进行插入排序,逐渐减小增量,最终实现对整个数据集合的排序。这样做减少了数据的搬移次数,提高了排序的效率。希尔排序通过这种分组的方式,使得较小的元素可以更快地移动到合适的位置,从而减少了插入排序中的反复比较和移动操作,提高了排序效率。

2.1 什么是希尔排序?

希尔排序是一种基于插入排序的排序算法,也被称为“缩小增量排序”。它的基本思想是将待排序的元素分成若干个小组,对每个小组进行插入排序;然后逐渐减小每组的元素个数,继续进行插入排序,直到每组只有一个元素为止。通过这种分组和逐渐减小增量的方式,希尔排序可以在一定程度上减少插入排序的移动操作次数,从而提高排序效率。

2.2 排序思路

采取先部分后整体的思路进行讲解

  • 部分
  1. 设置分组的间隔 gap。
  2. 将每个组看作一个新的数组进行插入排序。
  3. 插入排序的数组下标以及循环结束的条件需要改变,见下图解
  • 整体
  1. 重新设置分组的间隔gap,缩小组数,重复插入排序操作。
  2. 直至gap为1,对整体进行一次插入排序,则最终完成了对数组的排序。
  3. 关于gap的取值选择,目前尚无定论。取gap = gap / 3+1为例
    摘自《数据结构-用面向对象方法与C++描述》-殷人昆
     

2.3 C语言源码

void ShellSort(int* a, int n)
{int gap = n;//总逻辑while (gap > 1){gap = gap / 3 + 1;//多组排序逻辑for (int j = 0; j < gap; j++){//一组排序逻辑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;}}}}
}

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

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

相关文章

成都爱尔眼科蔡裕主任解说什么是近视性黄斑病变

近视性黄斑病变&#xff0c;属于黄斑病变的其中一种。 黄斑是眼内一个部位&#xff0c;它位于眼底的后极部&#xff0c;视网膜的中心部&#xff0c;管理着光、形、色。黄斑变性是指由于年龄、遗传、不良环境、慢性光损伤等各种因素的影响&#xff0c;使眼部视网膜处的黄斑发生…

Go 和 Delphi 定义可变参数函数的对比

使用可变参数函数具有灵活性、重用性、简化调用等优点&#xff0c;各个语言有各自定义可变参数函数的方法&#xff0c;也有通用的处理方法&#xff0c;比如使用数组、定义参数结构体、使用泛型等。 这里总结记录一下 go、delphi 的常用的定义可变参数函数的方式&#xff01; 一…

【机器学习系列】使用高斯贝叶斯模型进行数据分类的完整流程

目录 一、导入数据 二、选择特征 三、十折交叉验证 四、划分训练集和测试集 五、训练高斯贝叶斯模型 六、预测测试集 七、查看训练集和测试集上的分数 八、查看混合矩阵 九、输出评估指标 一、导入数据 # 根据商户数据预测其是否续约案例 import pandas #读取数据到 da…

如何部署一套高可用性的医院信息管理系统?基于华为云、SpringBoot、Vue及Jenkins、Gitlab的CI/CD流程

目录 一、项目背景 二、项目架构 三、项目部署流程 1、前端部署 2、后端部署 3、监控与运维 四、项目过程 一、项目背景 随着医疗信息化程度的不断加深&#xff0c;医院信息管理系统的稳定性和可用性成为了医疗机构日常运营的关键。在这个数字化时代&am…

ChatGPT魔法,定制个性化提示词!

扮演Prompt创作者的角色 我想让你成为我的Prompt创作者。你的目标是帮助我创建最佳的Prompt&#xff0c;这个Prompt将由 你ChatGPT使用。 你将遵循以下过程&#xff1a; 1.首先&#xff0c;你会问我Prompt是关于什么的。我会告诉你&#xff0c;但我们需要通过不断的重复来改进…

一些关于深度聚类以及部分对比学习的论文阅读笔记

目录 资料SwAV问题方法方法的创新点为什么有效有什么可以借鉴的地方聚类Multi-crop 代码 PCL代码 Feature Alignment and Uniformity for Test Time Adaptation代码 SimSiam 资料 深度聚类算法研究综述(很赞&#xff0c;从聚类方法和深度学习方法两个方面进行了总结&#xff0…

Linux查看设备信息命令

dmidecode | grep Product Name 查看grub版本号&#xff1a;rpm -qa | grep -i "grub" 客户端操作系统版本&#xff1a; cat /etc/issue cat /etc/redhat-release 处理器品牌及型号&#xff1a; less /proc/cpuinfo |grep model

【Unity入门】认识Unity编辑器

Unity 是一个广泛应用于游戏开发的强大引擎&#xff0c;从 1.0 版本开始到现在&#xff0c;其编辑器的基本框架一直保持稳定。其基于组件架构的设计&#xff0c;使得界面使用起来直观且高效。为了更好地理解 Unity 的界面&#xff0c;我们可以将其比喻为搭建一个舞台。以下是对…

uni微信小程序input框过滤中文字节以及规定以外的符号

问题描述 需求是输入账号只能为手机号、邮箱、字母和数字组成的字符串&#xff0c;那么就是所有大小写字母、数字、以及符号 - _ . 四种。 条件限制 微信小程序无法直接通过type属性实现&#xff0c;type属性中没有专门为只允许英文字母的输入类型。详情见input | uni-ap…

【windows】Total Uninstall:一款功能强大的完全卸载软件

软件介绍 Total Uninstall是一款专业的软件卸载工具&#xff0c;旨在帮助用户彻底地清除计算机上的应用程序&#xff0c;包括与应用程序相关的所有文件和注册表项。以下是Total Uninstall的一些主要功能和特点&#xff1a; 完全卸载&#xff1a;软件可以监视应用程序的安装过程…

使用Django实现WebSocket

文章目录 安装依赖编写Consumer配置路由在模板中使用WebSocket运行应用 WebSocket是一种在单个TCP连接上进行全双工通信的协议&#xff0c;在Web开发中被广泛应用于实时通信和数据推送。本文将介绍如何在Django中使用WebSocket来实现实时通信功能。 安装依赖 首先&#xff0…

基于Java实现震中附近风景区预警可视化分析实践

目录 前言 一、空间数据说明 1、表结构信息展示 2、空间范围查询 二、Java后台开发实现 1、模型层设计与实现 2、控制层设计与实现 三、Leaflet地图开发 1、地震震中位置展示 2、百公里风景区列表展示 3、风景区列表展示 4、附近风景区展示 四、总结 前言 地震这类…

prompt提示词:如何让AI帮你提一个好问题

我们看完一篇文章的时候&#xff0c;有时候发给AI后&#xff0c;不知道如何问AI&#xff0c;不知道问哪些问题&#xff0c;你使用这个提示词&#xff0c;就可以让AI帮你想一个好问题&#xff0c;然后你用AI想好的问题再去问AI 能提出一个好的问题是非常难的 提示词 结合文章…

免费插件集-illustrator插件-Ai插件-文本对象分行

文章目录 1.介绍2.安装3.通过窗口>扩展>知了插件4.功能解释5.总结 1.介绍 本文介绍一款免费插件&#xff0c;加强illustrator使用人员工作效率&#xff0c;进行文本对象分行。首先从下载网址下载这款插件 https://download.csdn.net/download/m0_67316550/87890501&…

【头歌】计算机网络DHCP服务器配置第二关access口配置答案

头歌计算机网络DHCP服务器配置第二关access口配置操作步骤 任务描述 本关任务&#xff1a;创建 vlan &#xff0c;并且将与 pc 机相连接口划分 vlan 。 操作要求 在第一关的拓扑图的基础上&#xff0c;配置交换机&#xff0c;具体要求如下&#xff1a; 1、在特权模式下进入 vla…

Day06-Mybatis

1. Mybatis介绍 2. Mybatis连接数据库并返回数据事例 连接oracle数据的设置方式 spring.application.namespringboot-mybatis spring.datasource.driver-class-nameoracle.jdbc.OracleDriver spring.datasource.urljdbc:oracle:thin:192.168.100.66:1521:orcl spring.datasour…

IDEA升级web项目为maven项目乱码

今天将一个java web项目改造为maven项目。 首先&#xff0c;创建一个新的maven项目&#xff0c;将文件拷贝到新项目中。 其次&#xff0c;将旧项目的jar包&#xff0c;在maven的pom.xml做成依赖 接着&#xff0c;把没有maven坐标的jar包在编译的时候也包含进来 <build>…

redis数据类型之string,list

华子目录 key操作说明SCAN cursor [MATCH pattern] [COUNT count]dump与restorekeys 通配符 示例演示 string说明setbit key offset valuegetbit key offsetsetrange key offset value List结构图相关命令lrem key count valueltrim key count value示例&#xff1a;使用 LTRIM…

从alpine构建预装vcpkg的docker image用于gitea actions CI

动机 想要构建一个基于vcpkg的交叉编译容器平台用于cpp项目的CI&#xff08;自动集成&#xff09;&#xff0c;此处仅提供最基础的image&#xff0c;amd64的机子上构建完成后大小为533兆&#xff08;着实不小&#x1f613;&#xff09;&#xff0c;各位看官可以在此基础上自行…

性能测试(一)—— 性能测试理论+jmeter的使用

1.性能测试介绍 定义&#xff1a;软件的性能是软件的一种非功能特性&#xff0c;它关注的不是软件是否能够完成特定的功能&#xff0c;而是在完成该功能时展示出来的及时性。 由定义可知性能关注的是软件的非功能特性&#xff0c;所以一般来说性能测试介入的时机是在功能测试完…