【数据结构】排序算法系列——希尔排序(附源码+图解)

2024-09-07 15:36

本文主要是介绍【数据结构】排序算法系列——希尔排序(附源码+图解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

希尔排序

算法思想

希尔排序(Shell Sort)是一种改进的插入排序算法,希尔排序的创造者Donald Shell想出了这个极具创造力的改进。其时间复杂度取决于步长序列(gap)的选择。我们在插入排序中,会发现是对整体数据直接进行了统一的插入排序,每个数据之间的间隙是1,这里的1指的就是步长序列gap。在希尔排序中,我们会将整体数据一分为多份,进行散布式的插入排序,这时候每一个子序列之间的间隙就是gap——那么事实上我们也可以将插入排序就看成是gap=1的希尔排序。

我们来具体分析希尔排序的算法步骤:

  • 将待排序序列分为若干个序列,每个序列的间距n(gap)需要相同
  • 将这些子序列分别进行插入排序
  • 不断减小这个间距

那么我们减小这个间距的目的是什么呢?

gap > 1时我们可以称为预排序,目的是让数组更接近于有序。当gap = 1时,数组已经接近有序的了,就整体而言,最后一次整体的插入排序就可以大大提高效率——我们从插入排序的时间复杂度分析也可以看出,越接近有序,插入排序的效率就越高,从而可以达到优化的效果。

图解

图片来源于网络

可以看到每次减小gap的规律是将原先的gap/2,但事实上这只是其中一种处理方法,并不说明这是最优解。

C语言代码分析

//与插入排序类似,只是插入排序的间隔是1,而希尔排序的间隔是gap//第一种思想:依次排序
//排完一组后,再排下一组
void ShellSort1(int arr[], int n)
{int gap = 3;//任意一个想要的间隔for (int j; j < gap; j++){for (int i = gap; i < n; i += gap){int end = i - gap;int tmp = arr[end + gap];while (end >= 0){if (tmp >= arr[end]){arr[end + gap] = tmp;end -= gap;}else{break;}}arr[end + gap] = tmp;}}}//第二种思想:多组并排
void ShellSort2(int arr[], int n)
{int gap = 3;//任意一个想要的间隔for (int i = gap; i < n-gap; i ++){int end = i;int tmp = arr[i + gap];while (end >= 0){if (tmp >= arr[end]){arr[end + gap] = tmp;end -= gap;}else{break;}}arr[end + gap] = tmp;}
}//gap越大,跳得越快,但一次排下来最无序
//gap越小,跳得越慢,但一次排下来更有序

注意

希尔排序实际上是个相当复杂的排序算法,这主要是跟它的步长序列gap到底该如何取、后续应该减小有关。这其中涉及到很多的数学分析以及数学公式,我们可以参考严蔚敏老师的解读:

在这里插入图片描述

以及殷人昆老师:

在这里插入图片描述

所以,本篇文章仅对其基本的算法思想和代码编写进行解析,如有兴趣深究希尔排序,各位读者们可以自行上网搜索有关知识~

时间复杂度

一般情况下,希尔排序的时间复杂度可以表示为:

  • 最好情况(已排序的情况):O(n log n)
  • 平均情况:取决于步长序列的选择,通常为**O(n1.3)-O(n2)**之间。
  • 最坏情况:O(n2)

希尔排序通过逐步减少步长来实现排序,初始的大步长使得数组元素可以较快地达到部分有序状态,最终通过小步长的插入排序完成排序。所以时间复杂度的具体分析也就取决于步长序列。

这里针对平均情况,我们进行一下简单的具体分析:

希尔排序的平均情况时间复杂度是比较复杂的。在实际应用中,常见的步长序列如希尔建议的序列(1, 3, 7, …, 2^k-1)或者Hibbard序列(1, 3, 7, 15, …, 2k-1)等,它们的时间复杂度通常就在**O(n1.3)-O(n2)**之间,这是经过数学算出来的结果。这些序列被设计为逐渐减小,从而在较早阶段快速减少逆序对的数量,然后在最后阶段完成排序。

总体来说,希尔排序的性能高度依赖于步长序列的选择。良好的步长序列可以显著改善排序的效率,使得平均情况下的时间复杂度能够在O(n^1.3)左右,而不好的选择则可能导致接近最坏情况的性能。

稳定性

鉴于希尔排序会改变前后元素的相对位置,所以:不稳定

这篇关于【数据结构】排序算法系列——希尔排序(附源码+图解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

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

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

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory