当前位置: 首页 > news >正文

C语言实现插入排序与希尔排序

目录

一,插入排序

插入排序C语言实现(升序)

1,将新元素插入到有序序列

2,循环的开始与终止 

二,希尔排序

希尔排序C语言实现(升序)

1,单趟:

2,循环及终止:


一,插入排序

插入排序的工作方式像许多人排序一手扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。
插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。

以将数组nums[9]={9,8,7,6,5,4,3,2,1}排为升序为例

 现在有九张扑克,我们摸到第一张9之后,我们认为一张牌就是有序的;然后我们摸到第二张牌8,为了将手中的牌排为升序(小的牌放左边,大的牌放右边),我们首先要比较摸到的牌和原先手里的牌的大小关系,发现8比9小,要放在9的左边。以此类推,每次都将摸到的牌与手里的牌进行比较,找到新牌合适的位置进行插入。

注意:因为从摸到第一张牌开始手里的牌就是有序的,所以手里的牌是有序的

插入排序C语言实现(升序)

可以发现,将新的元素插入到已经有序的序列中是一个循环过程,直到不再有要插入的元素

1,将新元素插入到有序序列

首先我们要清楚,新元素就是再有序序列之后的第一个元素,这个新元素和有序序列都是数组的元素。之所以要强调有序序列和新元素这两个概念,是为了更加直观的感受插入的过程

//代码不完整,仅仅示例
void InsetSort(int* nums, int numsSize)
{int end;int temp = nums[end+1];while (end >= 0 && nums[end] > temp){nums[end + 1] = nums[end];end--;}nums[end + 1] = temp;
}

 注释:

下标end表示有序序列的最后一个元素的下标,表示数组中下标0到end是有序的,temp储存的是新元素的值,也就是nums[end+1]。

为了将新元素插入到合适的位置,数组中下标为0到end+1的部分要进行数据的挪动,通过end遍历0到end这一部分元素,

如果end所指向的元素的值大于temp,则将其向后挪动一位,即nums[end + 1] = nums[end];如果end所指向的元素的值小于temp,则end+1的位置即为temp的位置

2,循环的开始与终止 

当end为0时,通过将新元素插入到有序序列中,使得数组下标0到1的部分变为有序,那么为了使整个数组有序,end需要从0到numsSize-1,逐步进行插入新元素,循环结束则排序完成

void InsetSort(int* nums, int numsSize)
{for (int i = 0; i < numsSize - 1; i++){int end = i;int temp = nums[i + 1];while (end >= 0 && nums[end] > temp){nums[end + 1] = nums[end];end--;}nums[end + 1] = temp;}
}

二,希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

注:希尔排序之所以高效,是因为插入排序的特性(一个数组越是接近有序,插入排序就越高效(若为有序数组,时间复杂度则为O(N))。希尔排序则依据此特性,先对数组进行数次预排序,使数组接近有序,最后再使用插入排序,完成升序

以将数组nums[9]={9,8,7,6,5,4,3,2,1}排为升序为例

初始状态:gap=9/2=4,数组分为4组,分别对每组进行插入排序

 迭代状态:gap=4/2=2,数组分为2组,分别对每组进行插入排序

终止状态:gap=2/2=1,数组分为1组,分别对每组进行插入排序,即对整个数组进行插入排序

希尔排序C语言实现(升序)

1,单趟:

每个分组(根据增量gap划分)之间进行插入排序;

2,循环及终止:

增量是变化的,当变为1时完成排序并结束

void ShellSort(int* nums, int numsSize)
{for (int gap = numsSize / 2; gap >= 1; gap /= 2){for (int i = 0; i < numsSize - gap; i++){int end = i;int temp = nums[end + gap];while (end >= 0 && nums[end] > temp){nums[end + gap] = nums[end];end -= gap;}nums[end + gap] = temp;}}
}

相关文章:

C语言实现插入排序与希尔排序

目录 一&#xff0c;插入排序 插入排序C语言实现&#xff08;升序&#xff09; 1&#xff0c;将新元素插入到有序序列 2&#xff0c;循环的开始与终止 二&#xff0c;希尔排序 希尔排序C语言实现&#xff08;升序&#xff09; 1&#xff0c;单趟&#xff1a; 2&#x…...

第九章-DOM与CSS

style属性 文档中每个元素节点都有一个属性style。style属性包含着元素样式&#xff0c;查询这个属性将返回一个对象而不是一个简单的字符串。样式都存放在这个style对象的属性里。 var element getElementById("example") //查看颜色属性 element.style.color //…...

蓝桥杯真题练习

小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 nn 个方格, 依次编号 1 至 nn, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。 小蓝开始…...

插入排序的简单理解

详细描述 插入排序的基本思想是&#xff1a;将一个记录插入到已经排好序的有序表中&#xff0c;从而得到一个新的、记录数增 1 的有序表。 在其实现过程中使用双层循环&#xff0c;外层循环针对除了第一个元素之外的所有元素&#xff0c;内层循环针对当前元素前面的有序表进行…...

Springboot框架集成Websocket通信方式

Websocket实现了“服务器”主动向“客户端”发送数据,改变了以往通过轮询、长轮训、长连接等方式获取服务器端数据的方式。 一、Websocket有三种不同的用场景,单播、广播和组播; (一)、单播(Unicast) 单播是客户端与服务器之间的“一对一”的连接。是在一个单个的发送…...

将json数据分组

在工作中有时需要根据业务需要&#xff0c;将大量数据进行处理分成几个一组 // 例如要将下方数据进行处理 var stuCount [{"id": "1612321835288","libraryCode": "D","regionCode": "A","positionCode&qu…...

从零开始实现一个C++高性能服务器框架----Socket模块

此项目是根据sylar框架实现&#xff0c;是从零开始重写sylar&#xff0c;也是对sylar丰富与完善 项目地址&#xff1a;https://gitee.com/lzhiqiang1999/server-framework 简介 项目介绍&#xff1a;实现了一个基于协程的服务器框架&#xff0c;支持多线程、多协程协同调度&am…...

ld: library not found for -lcrt0.o

ld: library not found for -lcrt0.o 背景&#xff1a; Mac 系统编译的时候报错 语言&#xff1a;golang 原因&#xff1a; 代码使用了静态编译&#xff0c;-static。stack overflow 上说 This option will not work on Mac OS X unless all libraries (including libgcc.a…...

接口测试和功能测试的区别有哪些?说一些你不知道的知识

目录 接口测试和功能测试的区别 目的 测试范围 测试方法 重要性 ​编辑 举个例子 对于接口测试 对于功能测试 ​编辑 总结 接口测试和功能测试是软件测试中的两种常见测试类型&#xff0c;主要用于评估软件系统的质量。尽管这两种测试都是为了评估软件系统的性…...

深度学习实战——不同方式的模型部署(CNN、Yolo)

忆如完整项目/代码详见github&#xff1a;https://github.com/yiru1225&#xff08;转载标明出处 勿白嫖 star for projects thanks&#xff09; 目录 系列文章目录 一、实验综述 1.实验工具及及内容 2.实验数据 3.实验目标 4.实验步骤 二、ML/DL任务综述与模型部署知识…...

【论文阅读】GNN阅读笔记

A gentle introduction on gnn 前言 发表在distill的文章 图神经网络在应用上才刚刚开始 搭建了一个GNN playground 什么是图 图是表示实体之间的关系 可以分别表示成点向量、边向量、图向量 图可以分为有向图和无向图 数据是怎么表示成图 图片表示成图&#xff1a; …...

QT常用控件——QTreeWidget(树控件),QTableWidget控件

目录 ★先开个小灶,在此插句话:【有关Halcon与Qt联编变量转换】 QTreeWidget树控件 QTableWidget控件...

为什么学校购买小型数控机床而不是大型工业数控机床?

CNC 机器是计算机控制的设备&#xff0c;可以高精度和准确度地切割、雕刻、钻孔或雕刻各种材料。 它们广泛应用于制造、工程、设计和艺术行业。 CNC 机器具有不同的尺寸和功能&#xff0c;从小型台式机到大型工业机型。 人们可能想知道为什么学校会选择购买小型 CNC 机器而不是…...

【Go自学】一文搞懂Go append方法

我们先看一下append的源码 // The append built-in function appends elements to the end of a slice. If // it has sufficient capacity, the destination is resliced to accommodate the // new elements. If it does not, a new underlying array will be allocated. //…...

【压测】通过Jemeter进行压力测试(超详细)

文章目录背景一、前言二、关于JMeter三、准备工作四、创建测试4.1、创建线程组4.2、配置元件4.3、构造HTTP请求4.4、添加HTTP请求头4.5、添加断言4.6、添加察看结果树4.7、添加Summary Report4.8、测试计划创建完成五、执行测试计划总结背景 通过SpringCloudGateway整合Nacos进…...

C# | 上位机开发新手指南(七)加密算法

上位机开发新手指南&#xff08;七&#xff09;加密算法 文章目录上位机开发新手指南&#xff08;七&#xff09;加密算法前言加密算法的分类对称加密算法和非对称加密算法流加密算法和块加密算法分组密码和序列密码哈希函数和消息认证码对称加密与非对称对称加密优点缺点对称加…...

实验一 跨VLAN访问

目录 一、按照拓扑图配置VLAN&#xff0c;并实现跨VLAN间的访问。 二、实验环境 三、实验步骤 一、按照拓扑图配置VLAN&#xff0c;并实现跨VLAN间的访问。 1、配置好交换机的VLAN和各个终端的地址&#xff0c;实现各个VLAN内能连通。 2、开启两个交换机的VTY连接&#xff0…...

通信算法之130:软件无线电-接收机架构

1. 超外差式接收机 2.零中频接收机 3.数字中频接收机...

C++编程大师之路:从入门到精通-C++基础入门

文章目录前言主要内容C基础入门初识C第一个C程序注释变量常量关键字标识符命名规则数据类型整型sizeof关键字实型&#xff08;浮点型&#xff09;字符型转义字符字符串型布尔类型 bool数据的输入运算符算术运算符赋值运算符比较运算符逻辑运算符程序流程结构选择结构if语句三目…...

如何在千万级数据中查询 10W 的数据并排序

前言 在开发中遇到一个业务诉求&#xff0c;需要在千万量级的底池数据中筛选出不超过 10W 的数据&#xff0c;并根据配置的权重规则进行排序、打散&#xff08;如同一个类目下的商品数据不能连续出现 3 次&#xff09;。 下面对该业务诉求的实现&#xff0c;设计思路和方案优…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...