加强网站网络安全建设,网站建设平台对比,帮别人做网站赚钱,培训公司网站建设前言#xff1a;学习希尔排序前最好先掌握插入排序#xff0c;在进行#xff1b;不会的可以点击——【排序算法】插入排序-CSDN博客 一、希尔排序#xff1a; 希尔排序#xff0c;也称为缩小增量排序#xff0c;是一种基于插入排序的快速改进算法。由Donald Shell于1… 前言学习希尔排序前最好先掌握插入排序在进行不会的可以点击——【排序算法】插入排序-CSDN博客 一、希尔排序 希尔排序也称为缩小增量排序是一种基于插入排序的快速改进算法。由Donald Shell于1959年提出。 它的基本思想是将待排序的元素按照一定的增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。希尔排序在一般用于处理大量数据 二、思路
分成2个阶段 1、预排序这个阶段将待排序的数据分成gap组对每组数据进行插入排序。 2、插入排序gap1时也就是只有1组的情况这个数组就变成有序数组了。 具体详情
1、将一个小于n元素个数的的整数作为gap增量所有距离为gap的元素作为一组数据也就是我们说的将数组分成gap组然后对每一组数据进行插入排序排好后取一个比第一增量小的整数比原gap小的组数重新将新的gap距离的元素作为一组数据接着上述操作重复这些操作
2、当gap不断细分到了gap1即将所有元素分为一组时进行插入排序数据变成有序
下面的动图我觉的比较直观的了当然没看懂也没关系下面会有讲解 先分组然后你会发现我们分了三组我们以3个元素为一组分的但是有的组元素个数未满三个因为元素之间的距离和数组长度的差异会有点不同但是影响不大哈值得注意的是距离差3不是元素个数差3哈个数是只差了2个元素从图里也可以看出来 分为3个组 第一组8、7、5 第二组9、2、4 第三组1、3 对第一组进行插入排序 然后接下来是下标为0gapgap的位置来一次插入排序该位置本来的元素是5经过插入排序后5到了这组数据的最前面此时这一组的数据是不是变成有序了 当每组都进行完插入排序后我们可以发现小的数几乎靠近左边大的数几乎靠近右边。大致粗略有点顺序了 然后将gap1进行一次整体的插入排序因为数据比较少 所以这里gap的分化次数也比较少 三、时间复杂度(有点难证明记住即可) ON^1.3 四、实现 先考虑一组的实现哈。发现了没其实和插入排序实现很相似如果gap1就是插入排序了。 对每一组都要进行插入发现了么先写底层逻辑真的很清晰我们会顺畅很多 但是我不想要三层循环嵌套可以修改一下之前是一组一组的进行就是说排好一组在进行另一组。现在我直接交错进行先第一组的第一个元素然后第二组的第一个元素然后第三组的第一个元素再是第一组的第二个元素…… 下标到最后一组倒数第二个元素的位置即可因为我们是将end的下一个元素抽出来注意不要越界访问 最后要完成gap的变化gap不是一直不变的会不断地变小直到gap1也就是第二个阶段对整个数组进行插入排序所以gap是个变值 整体代码
void ShellSort(int* a, int n)
{int gap n;//gap的组数越大数据可以更快的跳到后面小的更快跳到前面但是越不接近有序反之gap越接近有序while (gap 1){//巧妙的用的除法/2 /3 /4都行但是有人证明了/3更好还要加1因为gap小于3的话gap/30//最后一次gap一定是1,也就是插入排序数据变成有序的呢gap gap / 3 1;for (int i 0; i n - gap; i){//分组int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}} gap的选取 gap刚开始时从每组3个数据开始进行分组插入排序然后gapgap/31不断地分化组数分的组数在减少但是相反的每组数据个数在增加加一个 1 是为了保证最后一次满足gap1因为gap/3 gap小于3时得到的商只能是0并不是只能gap/3也可以gap/2等等但是目前gap/31是时间复杂度被验证过了的 分组组数的特点 gap越大每一组的数据间隔越大中间隔的元素个数多插入一次的幅度更大大的数据能够更快的跳到后面小的数据也能更快的跳到前面但是越远离有序 gep越小每组数据间隔越小中间隔的元素个数少此时数据跳到后面也就越慢小的数据跳到前面也越慢但是越接近有序即gap1时就是有序的 感 谢 观 看
