【数据结构】第十六弹---C语言实现希尔排序

个人主页: 熬夜学编程的小林

💗系列专栏: 【C语言详解】 【数据结构详解】【C++详解】

目录

1、希尔排序( 缩小增量排序 )

1.1、预排序实现

1.2、希尔排序代码实现

1.3、代码测试

1.4、时空复杂度分析

1.5、性能比较

总结


上一弹我们学习了直接插入排序,通过时空复杂度分析,时间复杂度为O(N^2),一般情况效率较低,有没有对直接插入排序进行优化的排序呢???没错,我们这一弹讲解的排序就是对直接插入排序的优化的排序!!!
 

1、希尔排序( 缩小增量排序 )

希尔排序是一种基于插入排序的算法,通过引入增量的概念来改进插入排序的性能

希尔排序法又称缩小增量法。希尔排序法的基本思想是:将原始列表分成多个子列表先对每个子列表进行插入排序,然后逐渐减少子列表的数量,使整个列表趋向于部分有序,最后当整个列表作为一个子列表进行插入排序时,由于已经部分有序,所以排序效率高。这个过程中,每次排序的子列表是通过选择不同的“增量”来确定的。

动图如下: 

实现思路

  1. 预排序
  2. 直接插入排序

1.1、预排序实现

预排序:

根据当前增量,数组被分为若干子序列,这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。

假设当前增量为5:

首先,增量为5,我们将数组元素分为增量(5)个子序列,每个子序列由原数组中相隔增量位置上的元素组成。所以我们有如下子序列:

子序列1: 9,4
子序列2: 1,8
子序列3: 2,6

子序列4: 5,3
子序列5: 7,5


然后对每个子序列进行独立的插入排序:

子序列1排序后:4,9
子序列2排序后:1,8
子序列3排序后:2,6

子序列2排序后:3,5
子序列3排序后:5,7

一趟排序之后的数组:

4 1 2 3 5 9 8 6 5 7

完成了一轮希尔排序,此时整个数组并不完全有序,但是已经比原始的数组更接近有序了。然后减小增量,通常是将原来的增量除以2(或者除以3+1),现在选择下一个增量为 2,按照此排序规则继续预排序即可,直到增量为1时,则为直接插入排序,此时则排序完成。

一个子序列排序实现:

int gap;
int end;
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;

与直接插入代码不同的是,这里对end所加减的均为gap;

单次插入完成后,我们来控制单个子序列的整个过程,每实现一次排序,下一次插入的数据为end+gap。

单趟排序实现:

int gap;for (int i = 0; i < n-gap; i += gap)
{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;
}

这里for循环的条件为 i <n-gap 防止数组越界.

完成单个子序列的排序后,我们再对整个子序列排序:

int gap;
for (int j = 0; j < gap; j++)
{for (int i = 0; i < n - gap; i += gap){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;}
}

外层循环(for (int j = 0; j < gap; j++))意在对每个以gap为间隔的分组进行遍历。

优化:

这串代码三层循环的逻辑是按照每一组排序完成后再进行下一组排序的,事实上我们可以不需要最外层的循环。

int gap = 3;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;
}

这里我们将原先代码中的i += gap修改为i++意味着这次不是按照一组一组进行了,是一次排序完每个组的第二个元素,再进行下一个元素的排序。 

1.2、希尔排序代码实现

我们先对预排序的增量进行分析:

gap越大,大的值更快调到后面,小的值更快调到前面,越不接近有序。
gap越小,大的值更慢调到后面,小的值更慢调到前面,越接近有序。
当gap为1,就是直接插入排序。

所以在实现希尔排序时,给gap固定值是行不通的。

因此,gap的值是应该随着n来变化的,实现多次预排。为了满足gap最终为1,博主推荐的方式是先将gap赋值成n,然后在排序的时候将gap赋值成gap/3+1(或者gap/2)

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//博主写的是/3+1也可以是gap/2for (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;}}
}

这里无论gap是奇数还是偶数,这里gap最终都会除以到值为1。

在这里:

gap>1时是预排序,目的让其接近有序
gap=1时是直接插入排序,目的让其有序。
在gap=1时,已经十分接近有序了。

这里gap预排序次数还是有点多,因此我们可以再次进行修改,让gap每次除以3,为了使gap最后能回到1,我们进行加一处理。

 注意:

1. 此处都是每隔gap进行插入。

2. gap不是一定为gap/3 + 1,也可以是gap /2 ,原因是当gap等于1的时候就是直接插入排序,进行一次排序即可变成有序,所以只要最后的gap为1都是可以的。 

1.3、代码测试

测试代码:

//测试希尔排序
int main()
{int a[] = { 9,8,7,6,5,4,3,2,1,0 };//给一组数据int sz = sizeof(a) / sizeof(a[0]);//计算数组元素个数printf("排序前:\n");ArrayPrint(a, sz);ShellSort(a, sz);printf("排序后:\n");ArrayPrint(a, sz);return 0;
}

测试结果:

1.4、时空复杂度分析

希尔排序的时间复杂度并不固定,它依赖于所选择的间隔序列(增量序列)。直到今天,已经有多种不同的间隔序列被提出来,每种都有自己的性能特点。

《数据结构(C语言版)》--- 严蔚敏
 

《数据结构-用面相对象方法与C++描述》--- 殷人昆

时间复杂度:

因为咋们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O(N^1.25) 到  O(1.6* N^1.25) 来算。

空间复杂度:

插入排序的空间复杂度为O(1),因为它是一个原地排序算法,不需要额外的存储空间来排序。

1.5、性能比较

我们在前面一弹提到了clock()函数可以获取程序启动到函数调用时之间的CPU时钟周期数,我们在这里通过具体的排序算法来进行比较性能。

注意:clock()函数的头文件是#include<time.h>,时间的单位为毫秒。

性能比较的思想是通过比较两个函数所运行的时间大小。通过clock计算排序前的程序运行的时间,再计算排序结束程序运行的时间,时间的差值则为排序运行的时间。

尽量使用release模式进行测试,因为release效率更高。

测试代码:

void TestOP()
{srand(time(0));//随机数种子const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);//动态开辟N个元素int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand() + i;//随机数只有3万,为了更加随机再加上ia2[i] = a1[i];}//clock计算程序运行到此时的时间 毫秒int begin1 = clock();//排序前程序运行时间InsertSort(a1, N);int end1 = clock();//排序后程序运行时间int begin2 = clock();ShellSort(a2, N);int end2 = clock();printf("InsertSort:%d\n", end1 - begin1);//程勋运行时间的差值即排序运行的时间printf("ShellSort:%d\n", end2 - begin2);free(a1);//释放空间free(a2);
}

当N为10万时,release版本测试出来的结果: 

 

 当N为100万时,release版本测试出来的结果: 

明显能够看到希尔排序的效率比直接插入排序的效率高很多,当N为10万的时候,希尔排序是直接插入排序的18倍,当N为10万的时候,希尔排序是直接插入排序的20倍。

希尔排序的特性总结:

时间复杂度:O(N²)

空间复杂度:O(1)

稳定性:不稳定

复杂性:简单

总结


本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

2024年【四川省安全员C证】考试题及四川省安全员C证考试资料

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 四川省安全员C证考试题是安全生产模拟考试一点通总题库中生成的一套四川省安全员C证考试资料&#xff0c;安全生产模拟考试一点通上四川省安全员C证作业手机同步练习。2024年【四川省安全员C证】考试题及四川省安全员…

SUSTAINABILITY,SCIESSCI双检期刊还能投吗?

本期&#xff0c;小编给大家介绍的是一本MDPI出版社旗下SCIE&SSCI双检“毕业神刊”——SUSTAINABILITY。据悉&#xff0c;早在2024年1月&#xff0c;ElSEVIER旗下的Scopus数据库已暂停收录检索期刊SUSTAINABILITY所发表文章&#xff0c;同时重新评估是否继续收录该期刊。随…

Carsim高级开发:VS Connect通讯开发指南

文章目录 前言一、VS Connect 概念引入二、VS Connect 通讯框架三、Carsim 工程配置1、车辆模型配置2、procedure配置3、Run Control配置4、受控车辆名称配置 四、VS Connect Server代码1、打开Sln工程2、代码修改 五、VS Connect Client代码1、函数的调用关系2、carsim_variab…

BetterZip 5软件安装包下载+安装教程

BetterZip是一款功能强大的Mac解/压缩软件&#xff0c;可以满足用户对文件压缩、解压、加密和保护等方面的需求。以下是关于BetterZip软件的主要功能、特点和使用方法的详细介绍&#xff0c;以及对其用户友好度、稳定性和安全性的评价。 安 装 包 获 取 地 址: BetterZip 5-安…

配置完eslint没有用?

当你使用 npx eslint --init 生成配置文件后 你也配置好了.prettierrc 当你在代码写一点小问题的时候 发现eslint没有进行检查 原因是你生成的 .eslintrc.js中没有加上这个配置 extends: [.....plugin:prettier/recommended],加上以后重启vscode你会发现

基于flask的网站如何使用https加密通信-问题记录

文章目录 项目场景&#xff1a;问题1问题描述原因分析解决步骤解决方案 问题2问题描述原因分析解决方案 参考文章 项目场景&#xff1a; 项目场景&#xff1a;基于flask的网站使用https加密通信一文中遇到的问题记录 问题1 问题描述 使用下面的命令生成自签名的SSL/TLS证书和…

传统边界安全设备的前世今生

光看不行得防御 只能抵御已知规则 识别病毒文件 识别方式是将数据包还原成文件&#xff0c;然后对文件进行病毒检测&#xff0c;检测方式就是以下三种 1、每一个文件都有一个独一无二的MD5值&#xff0c;把病毒文件的MD5值也进行记录&#xff0c;然后进行匹配 2、文件稍有变…

PS通过GTX实现SFP网络通信1

将 PS ENET1 的 GMII 接口和 MDIO 接口 通过 EMIO 方 式引出。在 PL 端将引出的 GMII 接口和 MDIO 接口与 IP 核 1G/2.5G Ethernet PCS/PMA or SGMII 连接&#xff0c; 1G/2.5G Ethernet PCS/PMA or SGMII 通过高速串行收发器 GTX 与 MIZ7035/7100 开发…

统计信号处理基础 习题解答10-17

题目&#xff1a; 在选择不含信息的或者不假设任何先验知识的先验PDF时,我们需要从数据中得到最大的信息量。在这种方式下,数据是了解未知参数的主要贡献者。利用习题10.15的结果,这种方法可以通过选择使I最大的来实现。对于例10.1的高斯先验PDF,该如何选择和2使得 是不含信息…

探索交互的本质:从指令到界面的演进与Linux基础指令的深入剖析

目录 1.指令 vs 界面//选读 1.1交互的需求 满足需求的第一阶段-指令 满足需求的第二阶段-界面 1.2 指令 和 界面交互 区别 2.操作系统介绍 2.1 举例说明 驱动软件层 2.2 为什么要有操作系统&#xff1f; 0x03 为什么要进行指令操作&#xff1f; 3.Linux基本指令 l…

并查集C++

并查集的原理 并查集&#xff08;Union-Find Set&#xff09;。可以把每个连通分量看成一个集合&#xff0c;该集合包含了连通分量中的所有点。这些点两两连通&#xff08;连通性&#xff09;&#xff0c;而具体的连通方式无关紧要&#xff0c;就好比集合中的元素没有先后顺序之…

C. Rooks Defenders(树状数组)

You have a square chessboard of size nnnn. Rows are numbered from top to bottom with numbers from 11 to nn, and columns — from left to right with numbers from 11 to nn. So, each cell is denoted with pair of integers (x,y)(x,y) (1≤x,y≤n1≤x,y≤n), where …

省去烦恼!轻松实现一台电脑登录多个微信号的秘诀揭秘!

你知道如何在同一台电脑上登录多个微信号&#xff0c;并实现聚合聊天吗&#xff1f; 今天&#xff0c;我将分享一个多微管理神器——个微管理系统&#xff0c;帮助你解决这一问题&#xff01; 1、多号同时登录&#xff0c;聚合聊天 无论你有多少个微信号&#xff0c;都可以一…

Sobel边缘检测

声明&#xff1a;学习过程中的知识总结&#xff0c;欢迎批评指正。 基本原理 灰度处理&#xff1a;边缘检测是基于图像亮度变化实现的&#xff0c;而图像的亮度信息通过灰度图像体现&#xff0c;因此需要把彩色图像转换成灰度图像。平滑处理&#xff1a;可以使用高斯滤波等滤…

Vscode flake8插件 python代码语法格式检测/代码过长等误报设置

在vscode中python格式检测使用flake8插件很方便&#xff0c;但是经常会报出一些不必要错误&#xff0c;影响开发效率&#xff0c;忽略这些错误可以帮助减少对于特定项目可能不太关键的PEP 8警告或代码风格问题的干扰&#xff0c;特别是在项目有自己的格式化和编码标准时。使用f…

Golang——gRPC gateway网关

前言 etcd3 API全面升级为gRPC后&#xff0c;同时要提供REST API服务&#xff0c;维护两个版本的服务显然不大合理&#xff0c;所以gRPC-gateway诞生了。通过protobuf的自定义option实现了一个网关。服务端同时开启gRPC和HTTP服务&#xff0c;HTTP服务接收客户端请求后转换为gr…

(微服务项目实战)预付卡系统券模块系统设计

1 技术架构 框架描述版本JDKJava运行环境17SpringBoot基于SpringBoot完成后端代码开发3.2.6DubboApache Dubbo 是一款易用、高性能的 WEB 和 RPC 框架&#xff0c;同时为构建企业级微服务提供服务发现、流量治理、可观测、认证鉴权等能力、工具与最佳实践3.xSpringCloud微服务…

WINUI——Trigger(触发器)使用小结

背景 WINUI不提供原生的Trigger支持&#xff0c;推荐使用VisualStateManager进行操作&#xff1b;然对于从WPF转WINUI的开发人员而言&#xff0c;经常会想用Trigger解决问题&#xff0c;鉴于此社区推出了CommunityToolkit.WinUI.Triggers以支持Trigger的使用。 使用方法 1.项…

Sky Master ULTIMATE Volumetric Skies Clouds Weather

该系统包含行业级优化的体积云、海洋系统、GI 代理,以及用于全局光照的优化 SEGI 和基于物理的天空渲染系统,且带有大气散射。 Sky Manager 可提供自动或按需的日/夜循环以及平滑的天气过渡。 Skybox 模式提供了与 Unity 及其功能(IBLGI、GI、Skybox)的完整集成。 先进的粒…

【YashanDB知识库】PHP使用ODBC驱动无法获取长度为256char以上的数据

【问题分类】驱动使用 【关键字】ODBC、驱动使用、PHP、 【问题描述】PHP使用PDO_ODBC连接yashan数据库&#xff0c;获取数据类型大于或等于varchar(256 char)的数据时出现异常&#xff0c;数据无法正常获取&#xff0c;BLOB等字段也无法正常获取&#xff0c;并且该问题会导致…