【数据结构】第十六弹---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.rhkb.cn/news/352875.html

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

相关文章

【达梦数据库】typeorm+node.js+达梦数据库返回自增列值

1.配置环境&#xff0c;下载依赖包 typeorm init --name test22 --database mysql typeorm-dm&#xff0c;uuid,typeorm2,修改连接信息 修改src/ data-source.ts 文件 连接dm&#xff0c;可参考刚刚安装typeorm-dm 模块中的 README.md 3.修改自增信息 /* 修改前*/PrimaryGen…

后端常见问题解答-位运算实际场景讲解

位运算 在计算机存储的世界中&#xff0c;一切都是二进制的&#xff0c;位运算就是对二进制位进行操作的一种运算。位运算是计算机中的一种常见运算&#xff0c;可以用来提高性能和提升代码的可读性。 位运算有很多种&#xff0c;比如与、或、非、异或等&#xff0c;这些运算…

Docker中部署Jenkins+Pipline流水线基础语法入门

场景 DockerCompose中部署Jenkins&#xff08;Docker Desktop在windows上数据卷映射&#xff09;&#xff1a; DockerCompose中部署Jenkins&#xff08;Docker Desktop在windows上数据卷映射&#xff09;-CSDN博客 DockerComposeJenkinsPipeline流水线打包SpringBoot项目(解…

Linux时间子系统6:NTP原理和Linux NTP校时机制

一、前言 上篇介绍了时间同步的基本概念和常见的时间同步协议NTP、PTP&#xff0c;本篇将详细介绍NTP的原理以及NTP在Linux上如何实现校时。 二、NTP原理介绍 1. 什么是NTP 网络时间协议&#xff08;英语&#xff1a;Network Time Protocol&#xff0c;缩写&#xff1a;NTP&a…

【docker入门】

在软件开发过程中&#xff0c;环境配置是一个至关重要的步骤&#xff0c;它不仅影响开发效率&#xff0c;也直接关联到软件的最终质量。正确的环境配置可以极大地减少开发中的潜在问题&#xff0c;提升软件发布的流畅度和稳定性。以下是几个关键方面&#xff0c;以及如何优化环…

编写一个简单的Mybatis插件

1.编写一个类&#xff0c;实现Intercepter这个接口 2.完成这个类的方法&#xff0c;并通过注解Intercepts来告诉Mybatis这个插件拦截哪个类和哪个方法 3.在Mybatis的全局配置文件里注册这个插件&#xff0c;让插件生效 4.玩一个实际功能的插件

MySQL 示例数据库大全

前言&#xff1a; 我们练习 SQL 时&#xff0c;总会自己创造一些测试数据或者网上找些案例来学习&#xff0c;其实 MySQL 官方提供了好几个示例数据库&#xff0c;在 MySQL 的学习、开发和实践中具有非常重要的作用&#xff0c;能够帮助初学者更好地理解和应用 MySQL 的各种功…

树莓派4B学习笔记8:开机自启动Python脚本_kill关闭后台脚本

今日继续学习树莓派4B 4G&#xff1a;&#xff08;Raspberry Pi&#xff0c;简称RPi或RasPi&#xff09; 本人所用树莓派4B 装载的系统与版本如下: 版本可用命令 (lsb_release -a) 查询: Opencv 版本是4.5.1&#xff1a; 紧接着上篇文章学习的串口通信,今日学习如何让树莓派开机…

使用MyBatisPlus让数据库和实体类字段自动映射

文章目录 使用MyBatisPlus让数据库和实体类字段自动映射需求场景假如没有映射把映射放到sql语句中使用MyBatisPlus提供的注解简化映射 使用MyBatisPlus让数据库和实体类字段自动映射 需求场景 数据库表中的字段名字&#xff0c;与实体类中的属性名字不一致&#xff0c;我们想…

【Linux】进程间通信2——命名管道

1. 命名管道(FIFO) 1.1. 基本概念 简单&#xff0c;给匿名管道起个名字就变成了命名管道 那么如何给 匿名管道 起名字呢&#xff1f; 结合文件系统&#xff0c;给匿名管道这个纯纯的内存文件分配 inode&#xff0c;将文件名与之构建联系&#xff0c;关键点在于不给它分配 D…

618数码好物清单,这些好物你不容错过

每次的618大促中&#xff0c;有各类数码产品纷纷亮相&#xff0c;让人眼花缭乱&#xff0c;而且打折的力度都很高&#xff0c;那么在这个充满诱惑的购物季里&#xff0c;哪些电子数码好物值得你入手呢&#xff1f;今天&#xff0c;我就一起给题主盘点那些实用至上、绝对不吃灰的…

RT-Thread-Nano使能动态内存Heap后,程序无法运行

RT-Thread-Nano移植 1. 动态内存堆1.1 问题1.2 解决 3. 问题根源 1. 动态内存堆 1.1 问题 按照官方文档&#xff1a;在 RT-Thread Studio 上使用 RT-Thread Nano&#xff0c;新建nano工程后&#xff0c;可以正常运行。 但是开启内存管理后&#xff0c;系统无法正常启动&…

Docker高级篇之轻量化可视化工具Portainer

文章目录 1. 简介2. Portainer安装 1. 简介 Portianer是一款轻量级的应用&#xff0c;它提供了图形化界面&#xff0c;用于方便管理Docker环境&#xff0c;包括单机环境和集成环境。 2. Portainer安装 官网&#xff1a;https://www.portainer.io 这里我们使用docker命令安装&…

三分钟了解链动3+1模式

在电商领域的营销策略中&#xff0c;链动31模式以其独特的魅力和优势&#xff0c;吸引了众多商家的目光。下面&#xff0c;我们将对这一模式进行深度剖析&#xff0c;并探讨其相较于链动21模式的优势所在。 一、身份设置与奖励机制 链动31模式在身份设置上分为三种&#xff1…

C#观察者模式应用

目录 一、什么是观察者模式 二、C#中观察者模式的实现 三、两种实现的用法 1、事件与委托 2、IObserver和IObservable 四、参考文献 一、什么是观察者模式 观察者&#xff08;Observer&#xff09;模式的定义&#xff1a;指多个对象间存在一对多的依赖关系&#xff0c;当…

C++: shared_ptr是线程安全的吗

导读 C面试中有时会有这样一个问题&#xff0c;shared_ptr是线程安全的吗&#xff1f;对此问题&#xff0c;我们需要从三个并发场景进行考虑&#xff0c;拷贝shared_ptr的安全性、对shared_ptr赋值的安全性和读写shared_ptr指向内存区域的安全性。 对于以上问题&#xff0c;首…

python flask配置数据库并进行orm操作 flask_sqlalchemy

&#x1f308;所属专栏&#xff1a;【Flask】✨作者主页&#xff1a; Mr.Zwq✔️个人简介&#xff1a;一个正在努力学技术的Python领域创作者&#xff0c;擅长爬虫&#xff0c;逆向&#xff0c;全栈方向&#xff0c;专注基础和实战分享&#xff0c;欢迎咨询&#xff01; 您的点…

Java——IO流(一)-(4/8):前置知识-字符集、UTF-8、GBK、ASCII、乱码问题、编码和解码等

目录 常见字符集介绍 标准ASCII字符集 GBK&#xff08;汉字内码扩展规范&#xff0c;国标&#xff09; Unicode字符集&#xff08;统一码&#xff0c;万国码&#xff09; 小结 字符集的编码、解码操作 方法 实例演示 常见字符集介绍 标准ASCII字符集 ASCll(American St…

YOLOv10改进 | 注意力篇 | YOLOv10改进CA注意力机制

1.CA介绍 摘要:最近关于移动网络设计的研究已经证明了通道注意力(例如,挤压和激励注意力)对于提升模型性能的显着有效性,但它们通常忽略了位置信息,而位置信息对于生成空间选择性注意力图很重要。 在本文中,我们通过将位置信息嵌入到通道注意力中,提出了一种新颖的移动…

伊拉克目的港清关严控,所有管控范围内的产品务必申请COC证书

伊拉克目的港清关严控&#xff0c;所有管控范围内的产品务必申请COC证书&#xff0c;COC/COI 伊拉克使馆认证&#xff0c;欢迎随时咨询小詹 近期&#xff0c;伊拉克海关扩大了进口产品管控品类&#xff0c;从产品的12大类700多种商品拓宽到800多种商品&#xff0c; 伊拉克海关…