数据结构|希尔排序

简介: 数据结构|希尔排序

介绍

最坏时间复杂度O(n^2)

希尔排序是插入排序的一种,是直接插入排序算法的一种更高效的改进版。(学习希尔排序之前需要了解插入排序)。

插入排序是每次向右移动一个步长的距离,对当前数值进行操作。而希尔排序就是加大插入排序的步长,这样可以使得元素可以一次性的朝最终位置前进一大步。

举例

给出一个无序列表(下图),假设希尔排序的gap(间隔/步长)为4,可以得到四个子序列,下标为0、4、8的序列1,下标为1、5的序列2,下标为2、6的序列3、下标为3、7的序列4。

之后对每个子序列进行插入排序

如对序列1进行插入排序,将78与53比较,再将21先78做比较、再与53做比较,得到排序后的序列:21、53、78。

对所有子序列进行插入排序后再重组得到下图

之后将步长缩小为2,重复上述操作,当步长为1时的操作结束后停止,就可以得到一个有序序列。

问题解答

可能很多人刚开始接触时,会觉得这样会使插入算法变得更复杂,好像执行的步骤增加了。不是这样,虽然希尔排序的最坏时间复杂度与插入算法相同,但希尔排序的最优时间复杂度是根据步长序列的不同而不同的,最好的情况下,时间复杂度可以降到O(n^1.3)。

那这个步长怎么取呢?这个难题至今没有解答,但经过大量的实验,人们还是积累了一定的经验。

在希尔的原稿中建议的初始步长是N/2,就是是将每一次排序分成两半,虽然这样取步长在大多数情况下仍然比插入排序好,但也算不上较好,网上可以搜出很多取法,感兴趣的可以搜来看看。这里我们就以希尔原稿中的步长来讲解。

代码实现

灰线左边是不需要移动的值,右边的值需要与左边作比较,因此每次循环都需要将右边的值与左边作比较。操作顺序:78、30、43、56、21。


78的下标是4也就是步长gap,那30的下标是gap+1,43是gap+2,56是gap+3,21是gap+4。

还记得上文说的,希尔算法其实就是插入算法的改进嘛,所以我们从插入算法入手。从内往外,先写每次需要执行的比较代码。

   1.先将一个子序列的灰线右边与左边做比较

   2.每个子序列执行的操作相同,用一个循环控制不同序列的内部比较

   3.此时一个步长所要执行的操作已结束,再用一个循环控制不同步长的操作



目录
打赏
0
0
0
0
14
分享
相关文章
数据结构与算法(Java篇)笔记--希尔排序
数据结构与算法(Java篇)笔记--希尔排序
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
62 10
数据结构算法--6 希尔排序和计数排序
**希尔排序**是插入排序的改进版,通过分组插入来提高效率。它逐步减少元素间的间隔(增量序列),每次对每个间隔内的元素进行插入排序,最终增量为1时进行最后一次直接插入排序,实现整体接近有序到完全有序的过程。例如,对数组`5, 7, 4, 6, 3, 1, 2, 9, 8`,先以间隔`d=4`排序,然后`d=2`,最后`d=1`,完成排序。计数排序则适用于0到100的数值,通过统计每个数出现次数,创建对应计数数组,再根据计数重建有序数组,时间复杂度为`O(n)`。
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
87 1
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
|
10月前
|
【C语言/数据结构】排序(直接插入排序|希尔排序)
【C语言/数据结构】排序(直接插入排序|希尔排序)
64 4
【数据结构与算法】:插入排序与希尔排序
欢迎大家来到初阶数据结构的最后一小节:排序
【数据结构与算法】:插入排序与希尔排序
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
116 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等