江西省城乡建设培训网 官方网站,wordpress 好不好,模板网免费下载素材,不会编码可以做网站优化吗#x1f493; 博客主页#xff1a;倔强的石头的CSDN主页 #x1f4dd;Gitee主页#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏#xff1a;《数据结构与算法》 期待您的关注 目录
一、引言
二、基本原理
三、实现步骤
四、C语言实现
五、性能分析
1. 时间复杂度… 博客主页倔强的石头的CSDN主页 Gitee主页倔强的石头的gitee主页 ⏩ 文章专栏《数据结构与算法》 期待您的关注 目录
一、引言
二、基本原理
三、实现步骤
四、C语言实现
五、性能分析
1. 时间复杂度近似为O(Nlog2N)
2. 空间复杂度O(1)
3. 稳定性不稳定的
六、优化
七、应用场景 一、引言 希尔排序Shell Sort是插入排序的一种更高效的改进版本也称为缩小增量排序。 希尔排序由Donald Shell于1959年提出并在其发表的论文“A high-speed sorting procedure”中详细描述了该算法。希尔排序的直接灵感来源于插入排序但它在插入排序的基础上进行了显著的改进旨在提高排序效率特别是针对大规模数据集。 想要读懂希尔排序最好先理解插入排序参考下面这篇文章 【数据结构与算法】深入解析插入排序算法原理、实现与优化-CSDN博客 二、基本原理 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行一次标准的直接插入排序。 这里的“基本有序”是指待排序的数组元素值满足某个增量序列的“局部有序”即对于某个变量gap序列中所有距离为gap的元素之间是有序的。随着变量gap的逐渐减小当gap减小到1时整个序列恰好被“基本有序”此时再对全体元素进行一次直接插入排序即可 三、实现步骤 1.外循环进行多轮预排序 选择一个变量序列
这个序列是逐渐减小的gap的值较大时数据可以更快的前后变动但不容易基本有序gap较小时数据前后变动较慢但更接近基本有序。 通常可以选取gap n/3, gap gap/3, ...直到gap 1。
但是要注意如果直接每次都/3可能面临的情况就是最后一组gap的值跳过了1比如n8时gap第一次等于2第二次等于0解决方法也很简单gap每次不是/3而是gapgap/31就可以让gap最后一次一定会减小到1 2.第二层循环每一轮预排序中进行分组 按gap进行分组根据当前的变量gap将待排序的数组元素下标按gap分组总共可以分成gap组。比如gap为3时每一组元素的首元素分别是012 3.第三层循环分组之后控制组里数据执行插入排序 每一组的数据有n/gap个下标为0gap, 2gap, 3gap,...的元素分为一组下标为1gap12gap13gap1……的元素分为一组……
这一层循环一个需要注意的细节就是预防数组的越界:每一组分组数据的最后一个数据一般不会是数组的最后一个数据。每次选取的要插入的数据下标是endgap那么这个下标不能超过n-gap。比如数组有10个元素gap为3第一组数据最后一个数据的下标是9要保证这一组数据访问到下标9之后不再向后访问因为下一次访问end为9要插入的数据9gap的位置已经没有数据了。 4.第四层循环实现插入排序的过程 每个数据向前扫描和移动找到合适的位置后插入直接在插入排序代码的基础上稍加修改即可 5.递减变量gap并重复上述分组排序过程
每完成一轮按变量gap的分组排序后将变量gap减小然后重复分组排序过程直到变量gap为1此时整个数组恰好被分成一组进行最后一次直接插入排序。 四、C语言实现
void ShellSort1(int* a, int n)//希尔排序升序
{int gap n;while (gap 1)//多组预排序最后一组gap1为直接插入排序{gap gap / 3 1;for (int i 0; i gap; i)//控制分组的组数gap组{for (int j i; j n - gap; j gap)//控制每组的插入元素个数n/gap个{int key a[jgap];int end j;while (end 0 a[end] key)//比较和移动元素{a[end gap] a[end];end - gap;}a[end gap] key;//满足大小关系后插入到指定位置}}}
}void ShellSort2(int* a, int n)//希尔排序降序
{int gap n;while (gap 1)//多组预排序最后一组gap1为直接插入排序{gap gap / 3 1;for (int i 0; i gap; i)//控制分组的组数gap组{for (int j i; j n - gap; j gap)//控制每组的插入元素个数n/gap个{int key a[j gap];int end j;while (end 0 a[end] key)//比较和移动元素{a[end gap] a[end];end - gap;}a[end gap] key;//满足大小关系后插入到指定位置}}}
} 五、性能分析
1. 时间复杂度近似为O(Nlog2N)
希尔排序的时间复杂度并不是一个定值它依赖于增量序列gap序列的选取。
平均时间复杂度在多数情况下希尔排序的平均时间复杂度可以近似为O(Nlog2N)但这并不是一个严格的结论因为实际性能会受到增量序列的具体选择和数据初始状态的影响。最佳时间复杂度在最佳情况下即数据已经接近有序时希尔排序可以接近线性排序的效率但具体数值难以准确给出。最差时间复杂度在最坏情况下希尔排序的时间复杂度仍然是O(N^2)。这通常发生在增量序列选择不当导致算法无法有效减少数据比较和移动次数时。
2. 空间复杂度O(1)
希尔排序是原地排序算法它只需要一个额外的空间来存储临时变量用于数据交换因此其空间复杂度为O(1)。这意味着希尔排序在排序过程中不会占用额外的存储空间这对于内存资源有限的环境非常有利。
3. 稳定性不稳定的
希尔排序是不稳定的排序算法。在排序过程中由于存在跳跃式的比较和移动相同元素的相对位置可能会发生变化。因此在需要保持元素原始顺序的场景中希尔排序可能不是最佳选择。 六、优化 将第二层第三层循环合为一层循环 以前是四层循环时我们是将分组作为一层循环每组里的数据插入作为一层循环 将两层循环合为一层之后不是一组一组进行预排序而是将数据逐个的与它对应的组里的数据进行预排序互不影响 优化之后代码更加简洁但效率没有提升 void ShellSort(int* a, int n)//希尔排序升序代码优化版效率没有提升
{int gap n;while (gap 1)//多组预排序最后一组gap1为直接插入排序{gap gap / 3 1;for (int i 0; i n - gap; i)//控制多组以及插入元素个数{int key a[i gap];int end i;while (end 0 a[end] key)//比较和移动元素{a[end gap] a[end];end - gap;}a[end gap] key;//满足大小关系后插入到指定位置}}
} 七、应用场景 希尔排序Shell Sort由于其实现简单且在某些情况下表现良好因此在一些特定的应用场景中得到了应用。以下是一些希尔排序可能适用的场景 中等规模数据集对于小到中等规模的数据集比如几千个元素希尔排序通常能够提供良好的性能。在这些情况下希尔排序可能比更复杂的排序算法如快速排序、归并排序等更容易实现且效率相当。 部分有序数据集如果数据集已经部分有序即元素接近它们的最终位置希尔排序可以利用这一点来更快地完成排序。因为希尔排序通过引入间隔gap来允许元素在更远的距离上进行交换这有助于减少数据移动的次数从而加速排序过程。 内存受限的环境希尔排序是原地排序算法只需要O(1)的额外空间。在内存受限的环境中如嵌入式系统或大型数据集排序时内存使用受到严格控制的场景这一点尤为重要。 实时系统在一些实时系统中排序操作的响应时间非常关键。希尔排序由于其实现简单且通常能够快速完成排序因此可能是一个不错的选择。尽管在最坏情况下其时间复杂度为O(N^2)但在实际应用中它往往能够更快地完成排序特别是在数据集部分有序或规模适中的情况下。 教育目的在教学和学习排序算法的过程中希尔排序是一个很好的例子因为它展示了如何通过引入简单的改进即间隔序列来显著提高基本排序算法如插入排序的性能。 然而需要注意的是对于非常大的数据集或对数据排序的稳定性有严格要求的应用场景希尔排序可能不是最佳选择。在这些情况下可能需要考虑使用更高效的排序算法如快速排序、归并排序或堆排序或稳定的排序算法如归并排序、冒泡排序等。 总之希尔排序适用于中等规模、部分有序、内存受限或需要快速响应的实时系统等场景。但在选择排序算法时还需要根据具体的应用需求和数据集特点进行综合考虑。
