网站模块源码,设计方案表网站名称,网页设计页面代码,无货源电商软件app希尔排序
算法思想
希尔排序#xff08;Shell Sort#xff09;是一种改进的插入排序算法#xff0c;希尔排序的创造者Donald Shell想出了这个极具创造力的改进。其时间复杂度取决于步长序列#xff08;gap#xff09;的选择。我们在插入排序中#xff0c;会发现是对整体…希尔排序
算法思想
希尔排序Shell Sort是一种改进的插入排序算法希尔排序的创造者Donald Shell想出了这个极具创造力的改进。其时间复杂度取决于步长序列gap的选择。我们在插入排序中会发现是对整体数据直接进行了统一的插入排序每个数据之间的间隙是1这里的1指的就是步长序列gap。在希尔排序中我们会将整体数据一分为多份进行散布式的插入排序这时候每一个子序列之间的间隙就是gap——那么事实上我们也可以将插入排序就看成是gap1的希尔排序。
我们来具体分析希尔排序的算法步骤
将待排序序列分为若干个序列每个序列的间距ngap需要相同将这些子序列分别进行插入排序不断减小这个间距
那么我们减小这个间距的目的是什么呢
当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)左右而不好的选择则可能导致接近最坏情况的性能。
稳定性
鉴于希尔排序会改变前后元素的相对位置所以不稳定
