泗县口碑营销互联网营销推荐咨询,seo建设网站,建筑类专业做教育的网站,韶关住房和城乡建设网站#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前正在学习c和算法 ✈️专栏#xff1a;数据结构 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助… 个人主页Weraphael ✍作者简介目前正在学习c和算法 ✈️专栏数据结构 希望大家多多支持咱一起进步 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注 目录 一、希尔排序的由来二、算法思路三、预排序代码实现四、如何选择gap五、代码实现(完整版)六、性能分析 一、希尔排序的由来 从直接插入排序中我们总结了(假定要求升序)当原数组是逆序的时候时间复杂度为O(N2)效率极低。博客地址点击跳转当原数组是接近升序或者已经是有序的那么时间复杂度就是O(N)此时效率最高。 因此又一位名叫希尔的大佬发现如果一开始就让数组内的元素接近有序的话那插入排序的效率不就大大提升了吗所以希尔排序是插入排序的优化。
二、算法思路
预排序 — 首先让序列中的元素接近有序。
那么如何进行预排序呢重点
其运用了 分组插排 的思想定义一个变量gap间隔为gap分为一组进行插入排序
最后再对数组进行插入排序即可。
【画图演示】 通过以上图片我们还可以总结一个规律gap为几就代表预排序有几组
接下来我们简单实现预排序的代码。
三、预排序代码实现
void ShellSort(int a[], int n)
{// 假设gap为3int gap 3;// 1. gap是几就代表有几组for (int i 0; i gap; i){// 2. 间隔为gap为一组进行插入排序for (int j i; j n - gap; j gap){// 下面基本都是插入排序的代码(类似)int end j;int temp a[j gap];while (end 0){if (temp a[end]){a[end gap] a[end];end - gap;}else{a[end gap] temp;}}a[end gap] temp;}}
}那么最后就要对整体进行插入排序这样就能完美实现希尔排序了。但是我们难道还要重新再其后再手搓一个插入排序吗理论上是可以的但是没必要。注意看当间隔gap为1时不就是插入排序了吗因此普通插入排序和gap是有关系的。那么应该如何选择gap呢
四、如何选择gap
gap越大跳的越快越不接近有序gap越小跳的越慢越接近有序。
可以为大家验证一下
当gap 3时 是不是越接近有序
当gap 5时 虽然也接近有序但是没有比gap 3更接近有序
那么gap到底取多少合适呢
解答gap应该要不断在变化。为什么呢开头的结论gap越大跳的越快越不接近有序gap越小跳的越慢越接近有序。如果gap是固定大小给大了越不接近有序给小了接近有序但是跳的慢。因此预排序的为了让更大的数更快的跳到后面越小数越快跳到前面。这就是为什么gap应该要不断的变化。 最初希尔大佬提出取gap / 2为什么呢因为一个数不断/2最后的结果一定为1那么在上面我们说过当gap 1就可以满足整体的插入排序就不需要再手搓普通插入排序了。 后来Knuth提出取gap gap / 3 11为了保证最后gap一定为1还有人提出取奇数好也有人提出gap互质好。但无论哪一种主张都没有得到证明。其实都是ok的
五、代码实现(完整版)
void ShellSort(int a[], int n)
{// 3. 如何取gap// gap最大可以取到整个数组的长度nint gap n;while (gap 1){// gap gap / 3 1; // 这也是okk的gap / 2;// 1. gap是几就代表有几组for (int i 0; i gap; i){// 2. 间隔为gap为一组进行插入排序for (int j i; j n - gap; j gap){int end j;int temp a[j gap];while (end 0){if (temp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] temp;}}}
}【结果展示】 六、性能分析
时间复杂度
希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算。Knuth大佬进行了大量的试验统计计算出希尔排序的时间复杂度大约为O(N^1.3)
但是我们可以用代码进行性能测试的对比 如图当数据个数是10w时插入排序和希尔排序时间效率如下所示 由此看出希尔排序还是非常的牛逼的~
有人想希尔排序在预排序的时候不是运用到很多的插入排序为什么其效率还是比插入排序高
原因是其实gap的取值决定数组内的元素是否接近有序gap越大排的也越快但越不接近有序gap越小排的也就越慢但越接近有序。所以一开始gap的值可以设为数组元素个数gap一定不可能超过数组元素个数每次进行/2不断缩小gap其实最后发现希尔排序的插入排序的次数其实是小于直接排序的插入次数的。
