[数据结构]插入和希尔排序

一、插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

1.实现思路:

1.将第一待排序序列第一个元素看做一个有序序列。

2.把第二个元素到最后一个元素当成是未排序序列。

3.从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

动图演示:

动图来源:1.3 插入排序 | 菜鸟教程 (runoob.com)

代码实现:

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){// [0, end] end+1int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

二、希尔排序

1.来源:

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。希尔排序是记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

————《百度文库》

2.基本思想:

先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

3.实现方式:

① 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。
② 所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序。
③ 取第二个增量d2小于d1重复上述的分组和排序,直至所取的增量dt=1(dt小于dt-l小于…小于d2小于d1),即所有记录放在同一组中进行直接插入排序为止。

4.希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。
2. gap > 1 时都是预排序,目的是让数组更接近于有序。当 gap == 1 时,数组已经接近有序的了,这样就
会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算,因为 gap 的取值方法很多,导致很难去计算,因此在好些树中给出的
希尔排序的时间复杂度都不固定:
《数据结构 (C 语言版 ) --- 严蔚敏

由于动图没找到,这里我就画图描述一下吧,.

现在我们有如下数据:

我们先选

gap=8;

第一趟排序:

然后

gap=gap/3+1--->gap=3

第二趟排序:

接着

gap=gap/3+1--->gap=2

第三趟排序:

最后

gap=gap/3+1--->gap=1

代码实现:

void ShellSort(int* a, int n)
{int gap = n;while (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 (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

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

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

相关文章

星光/宝骏/缤果/长安 车机CarPlay手机操作破解教程V2.0版本(无需笔记本、无需笔记本、无需笔记本)

之前写了个1.0版本&#xff0c;由于太局限&#xff0c;需要用到笔记本才能操作&#xff0c;很多车友反馈不方便。特此出个手机版教程&#xff0c;简单easy&#xff0c;妈妈再也不用担心我搞不定啦 一、准备工作 先卸载车机上的autokit 或者 智能互联 app&#xff0c;这步很关…

神策数据参与制定首份 SDK 网络安全国家标准

国家市场监督管理总局、国家标准化管理委员会发布中华人民共和国国家标准公告&#xff08;2023 年第 13 号&#xff09;&#xff0c;全国信息安全标准化技术委员会归口的 3 项国家标准正式发布。其中&#xff0c;首份 SDK 国家标准《信息安全技术 移动互联网应用程序&#xff0…

计算机网络——30SDN控制平面

SDN控制平面 SDN架构 数据平面交换机 快速、简单&#xff0c;商业化交换设备采用硬件实现通用转发功能流表被控制器计算和安装基于南向API&#xff0c;SDN控制器访问基于流的交换机 定义了哪些可以被控制哪些不能 也定义了和控制器的协议 SDN控制器&#xff08;网络OS&#…

【探讨】光场相机三维重建研究进展与展望

摘要&#xff1a;光场相机利用二维影像同时记录空间中光线的位置和方向信息&#xff0c;能够恢复相机内部的光场&#xff0c;为三维重建提供了新的解决思路。围绕光场相机的三维重建问题&#xff0c;本文综述了光场数据获取手段&#xff0c;梳理和讨论了针对光场相机的标定算法…

Redis命令-List命令

4.6 Redis命令-List命令 Redis中的List类型与Java中的LinkedList类似&#xff0c;可以看做是一个双向链表结构。既可以支持正向检索和也可以支持反向检索。 特征也与LinkedList类似&#xff1a; 有序元素可以重复插入和删除快查询速度一般 常用来存储一个有序数据&#xff…

如何在Windows 10中打开屏幕键盘?这里有详细步骤

本文解释了在Windows 10中打开或关闭屏幕键盘的不同方法&#xff0c;还解释了如何将屏幕键盘固定到开始菜单。 使用屏幕键盘的快捷键 如果你喜欢快捷方式&#xff0c;你会喜欢这个&#xff1a;按物理键盘上的WinCTRLO。这将立即显示屏幕键盘&#xff0c;而无需通过轻松使用。…

Jmeter参数化 —— 循环断言多方法

1、参数化接口测试数据 注意&#xff1a;csv文档参数化&#xff0c;里面有多少条数据&#xff0c;就要在线程组里循环多少次&#xff0c;不然就只执行一次 2、添加配置元件-计数器 关于计数器&#xff1a; ①Starting Value&#xff1a;给定计数器的初始值; ②递增&#xff1a…

机器学习之决策树现成的模型使用

目录 须知 DecisionTreeClassifier sklearn.tree.plot_tree cost_complexity_pruning_path(X_train, y_train) CART分类树算法 基尼指数 分类树的构建思想 对于离散的数据 对于连续值 剪枝策略 剪枝是什么 剪枝的分类 预剪枝 后剪枝 后剪枝策略体现之威斯康辛州乳…

【LeetCode热题100】236. 二叉树的最近公共祖先(二叉树)

一.题目要求 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可…

ES6 学习(三)-- es特性

文章目录 1. Symbol1.1 使用Symbol 作为对象属性名1.2 使用Symbol 作为常量 2. Iterator 迭代器2.1 for...of循环2.2 原生默认具备Interator 接口的对象2.3 给对象添加Iterator 迭代器2.4 ... 解构赋值 3. Set 结构3.1 初识 Set3.2 Set 实例属性和方法3.3 遍历3.4 相关面试题 4…

用 SpringBoot+Redis 解决海量重复提交问题

1前言 在实际的开发项目中,一个对外暴露的接口往往会面临很多次请求&#xff0c;我们来解释一下幂等的概念&#xff1a;任意多次执行所产生的影响均与一次执行的影响相同。按照这个含义&#xff0c;最终的含义就是 对数据库的影响只能是一次性的&#xff0c;不能重复处理。如何…

100套HTML静态网页模板源码

源码介绍 100套HTML静态网页模板&#xff0c;设计的十分有特色&#xff0c;由于Github服务器原因可能下载速度较慢&#xff0c;已全部打包整理。 源码截图 源码下载 链接&#xff1a;https://pan.baidu.com/s/1dtAeaUUIZJM6ueqA30nQ2g?pwdy5qd 提取码&#xff1a;y5qd

SpringBoot集成WebSocket(实时消息推送)

&#x1f353; 简介&#xff1a;java系列技术分享(&#x1f449;持续更新中…&#x1f525;) &#x1f353; 初衷:一起学习、一起进步、坚持不懈 &#x1f353; 如果文章内容有误与您的想法不一致,欢迎大家在评论区指正&#x1f64f; &#x1f353; 希望这篇文章对你有所帮助,欢…

MySQL---触发器

一、介绍 触发器是与表有关的数据库对象&#xff0c;指在insert/update/delete之前(BEFORE)或之后(AFTER)&#xff0c;触发并执行触发器中定义的SQL语句集合。触发器的这种特性可以协助应用在数据库端确保数据的完整性, 日志记录 , 数据校验等操作 。 使用别名OLD和NEW来引用触…

快速上手Spring Cloud 七:事件驱动架构与Spring Cloud

快速上手Spring Cloud 一&#xff1a;Spring Cloud 简介 快速上手Spring Cloud 二&#xff1a;核心组件解析 快速上手Spring Cloud 三&#xff1a;API网关深入探索与实战应用 快速上手Spring Cloud 四&#xff1a;微服务治理与安全 快速上手Spring Cloud 五&#xff1a;Spring …

Nagios工具

一 nagios 相关概念 Nagios 是一款开源的免费网络监视工具&#xff0c;能有效监控 Windows、Linux 和 Unix 的主机状态&#xff0c;交换机路由器等网络设置&#xff0c;打印机等。在系统或服务状态异常时发出邮件或短信报警第 一时间通知网站运维人员&#xff0c;在状态恢复后…

让机器理解语言,从字词开始,逐步发展到句子和文档理解:独热编码、word2vec、词义搜索、句意表示、暴力加算力

让机器理解语言&#xff0c;从字词开始&#xff0c;逐步发展到句子和文档理解&#xff1a;独热编码、词嵌入、word2vec、词义搜索、句意表示、暴力加算力 独热编码&#xff1a;分类 二进制特征Word2Vec 词嵌入&#xff1a; 用低维表示 用嵌入学习 用上下文信息Skip-gram 跳字…

【JavaScript】数组 ② ( JavaScript 数组索引 | JavaScript 遍历数组 | 使用 for 循环遍历数组 )

文章目录 一、JavaScript 数组索引1、数组索引2、数组索引 - 代码示例 二、JavaScript 遍历数组1、使用 for 循环遍历数组2、使用 for 循环遍历数组 - 代码示例 一、JavaScript 数组索引 1、数组索引 在 JavaScript 中 , 数组 的 " 索引 " 又称为 " 下标 "…

ssm 房屋销售管理系统开发mysql数据库web结构java编程计算机网页源码eclipse项目

一、源码特点 ssm 房屋销售管理系统是一套完善的信息系统&#xff0c;结合springMVC框架完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模…

JAVAEE——线程池

文章目录 线程池的概念什么是线程池&#xff1f; 标准库中的线程池线程池的创建工厂模式工厂模式的用途线程池涉及到的类有哪些Executor接口ExecutorService接口Executors工厂类AbstractExecutorService虚类ThreadPoolExecutor普通类ThreadPoolExecutor内部的实现4个拒绝策略 线…