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

C++中常用的十大排序方法之4——希尔排序

    成长路上不孤单😊😊😊😊😊😊

【😊///计算机爱好者😊///持续分享所学😊///如有需要欢迎收藏转发///😊】

今日分享关于C++中常用的排序方法之4——希尔排序的相关内容!

关于【C++中常用的排序方法之4——希尔排序】

目录:

  • 一、希尔排序的定义
  • 二、希尔排序的发展历史
  • 三、希尔排序的的排序过程
  • 四、希尔排序的基本原理
  • 五、希尔排序的的特点
  • 六、希尔排序的的优点
  • 七、希尔排序的的缺点

希尔排序Shell Sort)

一、希尔排序的定义

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

  

二、希尔排序的发展历史

希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由希尔在 1959 年所发表的论文“A high-speed sorting procedure” 中所描述。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

1、插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。

2、但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

1961年,IBM 公司的女程序员 Marlene Metzner Norton(玛琳·梅茨纳·诺顿)首次使用 FORTRAN 语言编程实现了希尔排序算法。在其程序中使用了一种简易有效的方法设置希尔排序所需的增量序列:第一个增量取待排序记录个数的一半,然后逐次减半,最后一个增量为 1。该算法后来被称为 Shell-Metzner 算法 ,Metzner 本人在2003年的一封电子邮件中说道:“我没有为这种算法做任何事,我的名字不应该出现在算法的名字中。”

三、希尔排序的排序过程

1、缩小增量

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

排序过程:先取一个正整数d1数组元素放一组,组内进行直接插入排序;然后取d2

三趟结果

04 13 27 38 49 49 55 65 76 97

2、Shell排序

Shell排序的算法实现:

1. 不设监视哨的算法描述

void ShellPass(SeqList R,int d)

{//希尔排序中的一趟排序,d为当前增量

for(i=d+1;i

if(R[ i ].key

R[0]=R[i];j=i-d; //R[0]只是暂存单元,不是哨兵

do {//查找R的插入位置

R[j+d]=R[j]; //后移记录

j=j-d; //查找前一记录

}while(j>0&&R[0].key

R[j+d]=R[0]; //插入R到正确的位置上

} //endif

该方法实质上是一种分组插入方法

比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。

一般的初次取序列的一半为增量,以后每次减半,直到增量为1。

给定实例的shell排序的排序过程

假设待排序文件有10个记录,其关键字分别是:

49,38,65,97,76,13,27,49,55,04。

增量序列的取值依次为:

5,2,1

四、‌希尔排序的基本原理

希尔排序是基于插入排序的一种改进算法。它将整个待排序的记录序列分割成若干子序列,分别进行直接插入排序。然后逐渐减小间隔,再次进行插入排序,直到整个序列变为有序。希尔排序通过分组插入的方式,每次比较相距较远的元素,从而减少了逆序对的数量,提高了排序效率。

五、希尔排序的特点

希尔排序‌是一种高效的排序算法,由美国计算机科学家Donald Shell于1959年提出。它是插入排序的一种改进版本,通过分组插入排序和缩小增量的方式,大幅度减少了逆序对的数量,从而提高了排序效率。以下是希尔排序的主要特点:

分组插入排序‌:希尔排序将数组分成若干个子序列,每个子序列通过插入排序进行排序。由于子序列的长度较短,插入排序的时间复杂度较低,从而提高了排序效率‌。

缩小增量‌:希尔排序通过逐步缩小增量(通常采用二分法递减增量),将数组分成更小的子序列进行排序。增量最终减小到1时,整个数组进行一次插入排序‌。

大幅度减少逆序对‌:由于希尔排序是通过间隔分组进行插入排序的,每次排序都会将相距较远的元素进行比较和交换,从而大幅度减少了逆序对的数量。逆序对的数量是衡量一个排序算法效率的重要指标,逆序对越少,排序效率越高‌。

非稳定性‌:希尔排序是一种非稳定的排序算法。在排序过程中,相同大小的元素可能会发生交换,导致原来相对顺序的改变。尽管如此,希尔排序在实际应用中并不影响排序结果的正确性‌。

适用场景‌:希尔排序适用于大部分情况,尤其适用于部分有序的数据集。当数据集接近有序时,希尔排序的效率非常高‌。

六、希尔排序的优点

希尔排序的优点主要包括以下几个方面‌:‌

减少比较次数‌:希尔排序通过分组插入的方式进行排序,每次比较相距较远的元素,从而大幅度减少了逆序对的数量,提高了排序效率。

高效处理大数据量‌:希尔排序在处理大量数据时表现出色,其时间复杂度通常为O(n^1.3),并且空间复杂度为O(1),这意味着它需要的额外空间非常小。

简单易实现‌:希尔排序的实现相对简单,易于理解和编写代码。

适用于大规模数据‌:希尔排序特别适合处理大规模数据,因为它通过分组和逐步减小增量来排序,避免了直接对整个数据集进行排序的时间和空间复杂度过高的问题。

七、希尔排序的缺点

非稳定性‌:希尔排序是一种非稳定的排序算法,可能会改变相同元素的相对顺序。

性能受增量序列影响‌:增量序列的选择对希尔排序的性能有很大影响。如果增量序列选择不当,可能会导致时间复杂度退化为O(n^2)甚至更差。

时间复杂度不确定‌:希尔排序的时间复杂度并不固定,通常认为是O(n^1.3),但最坏情况下可能会更差。

七、插入排序的缺点

插入排序的主要缺点包括以下几个方面‌:

时间复杂度较高‌:插入排序的时间复杂度在最坏的情况下是O(n^2),其中n是待排序元素的数量。这意味着当数据量较大时,插入排序的效率会显著下降,不适合处理大规模数据集‌。

不适用于部分有序的数据‌:虽然插入排序在数据部分有序的情况下表现较好,但如果数据已经接近排序状态,其他排序算法(如归并排序或快速排序)通常会更高效‌。

不稳定‌:插入排序是一种不稳定的排序算法,相同的元素在排序后可能会改变它们原有的顺序。这意味着如果输入数组中有重复的元素,排序后这些元素的相对顺序可能会发生变化‌。

不适合实时应用‌:由于插入排序的时间复杂度较高,它不适合需要快速响应的应用场景,如实时数据处理系统‌。

相关文章:

C++中常用的十大排序方法之4——希尔排序

成长路上不孤单😊😊😊😊😊😊 【😊///计算机爱好者😊///持续分享所学😊///如有需要欢迎收藏转发///😊】 今日分享关于C中常用的排序方法之4——希尔排序的相…...

扶摇计划--从失业的寒冬,慢慢的走出来

作为资深 Java 开发工程师,你有丰富的技术经验和解决问题的能力,即使暂时失业,也可以通过多种方式赚取收入。以下是结合你的技能和市场需求的具体建议,分阶段规划实现: 第一阶段:快速变现(短期,1-3个月) 自由职业与远程工作 平台接单:在 Upwork、Freelancer 或国内平…...

unity学习24:场景scene相关生成,加载,卸载,加载进度,异步加载场景等

目录 1 场景数量 SceneManager.sceneCount 2 直接代码生成新场景 SceneManager.CreateScene 3 场景的加载 3.1 用代码加载场景,仍然build setting里先加入配置 3.2 卸载场景 SceneManager.UnloadSceneAsync(); 3.3 同步加载场景 SceneManager.LoadScene 3.3.…...

[cg] 使用snapgragon 对UE5.3抓帧

最近想要抓opengl 的api,renderdoc在起应用时会闪退(具体原因还不知道),试了下snapgraon, 还是可以的 官网需要注册登录后下载,官网路径:Developer | Qualcomm 为了方便贴上已经下载好的exe安装包&#x…...

一元函数微积分的几何应用:二维平面光滑曲线的曲率公式

文章目录 前言曲率和曲率半径的定义曲率计算公式参数方程形式直角坐标显式方程形式极坐标形式向量形式 前言 本文将介绍二维平面光滑曲线的曲率定义以及不同形式的曲率及曲率半径公式的推导。 曲率和曲率半径的定义 (关于二维平面光滑曲线的定义以及弧长公式请参…...

ISBN 号码——蓝桥杯

1.题目描述 每一本正式出版的图书都有一个 ISBN 号码与之对应,ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符,其规定格式如 “x-xxx-xxxxx-x”,其中符号“-”是分隔符(键盘上的减号),最后一位是识别码&a…...

Spring Boot - 数据库集成06 - 集成ElasticSearch

Spring boot 集成 ElasticSearch 文章目录 Spring boot 集成 ElasticSearch一:前置工作1:项目搭建和依赖导入2:客户端连接相关构建3:实体类相关注解配置说明 二:客户端client相关操作说明1:检索流程1.1&…...

51单片机CLD1602显示万年历+闹钟+农历+整点报时

1. 硬件设计 硬件是我自己设计的一个通用的51单片机开发平台,可以根据需要自行焊接模块,这是用立创EDA画的一个双层PCB板,所以模块都是插针式,不是表贴的。电路原理图在文末的链接里,PCB图暂时不选择开源。 B站上传的…...

C++ 中的类(class)和对象(object)

在 C 中,类(class)和对象(object)是面向对象编程(OOP)的核心概念。类是一种用户自定义的数据类型,它将数据(成员变量)和操作这些数据的函数(成员函…...

安卓通过网络获取位置的方法

一 方法介绍 1. 基本权限设置 首先需要在 AndroidManifest.xml 中添加必要权限&#xff1a; xml <uses-permission android:name"android.permission.INTERNET" /> <uses-permission android:name"android.permission.ACCESS_NETWORK_STATE" /&g…...

2025 年,链上固定收益领域迈向新时代

“基于期限的债券市场崛起与 Secured Finance 的坚定承诺” 2025年&#xff0c;传统资产——尤其是股票和债券——大规模涌入区块链的浪潮将创造历史。BlackRock 首席执行官 Larry Fink 近期在彭博直播中表示&#xff0c;代币化股票和债券将逐步融入链上生态&#xff0c;将进一…...

npm启动前端项目时报错(vue) error:0308010C:digital envelope routines::unsupported

vue 启动项目时&#xff0c;npm run serve 报下面的错&#xff1a; error:0308010C:digital envelope routines::unsupported at new Hash (node:internal/crypto/hash:67:19) at Object.createHash (node:crypto:133:10) at FSReqCallback.readFileAfterClose [as on…...

11.QT控件:输入类控件

1. Line Edit(单行输入框) QLineEdit表示单行输入框&#xff0c;用来输入一段文本&#xff0c;但是不能换行。 核心属性&#xff1a; 核心信号&#xff1a; 2. Text Edit(多行输入框) QTextEdit表示多行输入框&#xff0c;也是一个富文本 & markdown编辑器。并且能在内容超…...

deepseek核心技术:MLA架构-多头潜在注意力

deepseek核心技术:MLA架构-多头潜在注意力 MLA架构即Multi-Head Latent Attention(多头潜在注意力)架构,是一种优化后的注意力机制。以下是对其及相关示例的具体介绍: 工作原理 输入嵌入:将输入序列中的每个元素转换为向量表示,即嵌入向量。例如在处理文本时,将文本中…...

讯飞星火大模型API使用Python调用

本文仅仅为简单API调用&#xff0c;更多复杂使用方法请参见接口文档 先在科大讯飞开放平台注册账号&#xff0c;点击控制台&#xff0c;在我的应用中创建新应用&#xff0c;新应用的名称可以自定义&#xff0c;这里我写的是ai对话&#xff1a; 在这里我们使用的模型为Speak Ul…...

C#面试常考随笔7:什么是匿名⽅法?还有Lambda表达式?

匿名方法本质上是一种没有显式名称的方法&#xff0c;它可以作为参数传递给需要委托类型的方法&#xff0c;常用于事件处理、回调函数等场景&#xff0c;能够让代码更加简洁和紧凑。 使用场景 事件处理&#xff1a;在处理事件时&#xff0c;不需要为每个事件处理程序单独定义…...

Elasticsearch:如何搜索含有复合词的语言

作者&#xff1a;来自 Elastic Peter Straer 复合词在文本分析和标记过程中给搜索引擎带来挑战&#xff0c;因为它们会掩盖词语成分之间的有意义的联系。连字分解器标记过滤器等工具可以通过解构复合词来帮助解决这些问题。 德语以其长复合词而闻名&#xff1a;Rindfleischetik…...

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】1.25 视觉风暴:NumPy驱动数据可视化

1.25 视觉风暴&#xff1a;NumPy驱动数据可视化 目录 #mermaid-svg-i3nKPm64ZuQ9UcNI {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-i3nKPm64ZuQ9UcNI .error-icon{fill:#552222;}#mermaid-svg-i3nKPm64ZuQ9UcNI …...

idea maven本地有jar包,但还要从远程下载

idea 中&#xff0c;java 工程执行 maven reimport&#xff0c;报jar报无法下载。 我奇了个怪&#xff0c;我明明在本地仓库有啊&#xff0c;你非得从远程下载&#xff1f; 我从供应商那里拿来的&#xff0c;远程当然没有了。 这太奇葩了吧&#xff0c;折腾好久不行。 后来…...

C++编程语言:抽象机制:模板(Bjarne Stroustrup)

目录 23.1 引言和概观(Introduction and Overview) 23.2 一个简单的字符串模板(A Simple String Template) 23.2.1 模板的定义(Defining a Template) 23.2.2 模板实例化(Template Instantiation) 23.3 类型检查(Type Checking) 23.3.1 类型等价(Type Equivalence) …...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...