当前位置: 首页 > 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;设计思路和方案优…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...