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

2024-06-15 14:12

本文主要是介绍【数据结构】第十六弹---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)

稳定性:不稳定

复杂性:简单

总结


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

这篇关于【数据结构】第十六弹---C语言实现希尔排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063684

相关文章

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、