计科专业毕设做网站,傻瓜式做网站程序,什么网站做的产品海报比较多,开发一个页面多少钱一#xff1a;基本思想
先选定一个整数gap#xff0c;把待排序文件中所有记录分成个组#xff0c;按照所有距离为整数gap的记录分在同一组内#xff0c;并对每一组内的记录进行排序。然后#xff0c;通过整数gap逐渐变小#xff0c;重复上述分组和排序的工作。当整数gap…一基本思想
先选定一个整数gap把待排序文件中所有记录分成个组按照所有距离为整数gap的记录分在同一组内并对每一组内的记录进行排序。然后通过整数gap逐渐变小重复上述分组和排序的工作。当整数gap变小到达1时也就是执行插入排序这样所有记录在统一组内就排好序了。 所以一定得先理解插入排序-CSDN博客
不然很难理解此博客
二预排序的意义
Q既然最后都要执行插入排序那多一步预排序不是会徒增运算了
A预排序的意义在于让最后一步的插入排序的运算量大大的减小比直接的单独的插入排序更优 三预排序的核心
正如希尔排序的思想我们需要一个整数gap这个整数gap会逐渐变小最终变小到1为止
一般是gap 初始化为N也就是数组的元素个数然后在循环中 gap gap/2 这样每次进入循环这个gap就 /2会逐渐的减小最终为1跟着除法原则一个大于2的数不断的/2一定会有一次为1
例子 解释
1
gap N10
gap gap/2 5
根据思想可知gap为5即按照所有距离下标差值为5的记录分在同一组内如图内的
第一组9 4
第二组1 8
第三组2 6
第四组5 3
第五组7 5
然后每组进行组内的排序
第一组4 9
第二组1 8
第三组2 6
第四组3 5
第五组5 7
也就是上图中的 2
gap gap/2 2 此时的gap变成2所以
第一组4 2 5 8 5
第二组1 3 9 6 7
然后进行每组的组内排序
第一组2 4 5 5 8
第二组1 3 6 7 9
也就是上图中的 3 gap gap/2 1 gap为1
只有一组2 1 4 3 5 6 5 7 8 9
组内排序后
1 2 3 4 5 5 6 7 8 9
也就是上图中的 说白了gap为1 的时候进行的就是一次插入排序而且可以看的出来最后一次插入排序之前 我们接收到的数组已经有了一定的顺序。
下面是博主找到的一个动态演示图不过数据和上面的不一样一样的也是gap 5 到 gap 2再到最后的 gap 1 四代码展示
//希尔排序的第一种写法双for
void ShellSort(int* arr, int N)
{//gap初识为N元素的个数int gap N;//gap不为1就要继续的缩小并排序while (gap 1){//gap缩小gap gap / 2;//这个for控制每组的元素for (int j 0; j gap; j){ //这个for控制每组内的排序for (int i j; i N - gap; i gap){int end i;//即将排序的元素保留在tmpint tmp arr[end gap];//end0代表还有元素未比较while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}//来到这里分为两种情况 //1break-遇到比元素tmp小或和tmp相等的将m放在它的后面//2全部比较完了都没有遇到tmp的最后tmp放在数组第一个位置arr[end gap] tmp;}}}}
}
解释
1跟纯粹的插入排序相比咱们多了一个控制每组的元素的for循环 以及多了一个while来确保gap最后为1执行完排序才终止
2第二个for循环
该for循环控制的是每组元素的内部排序可以看作插入排序不过元素是间隔的iN-gap和插入排序中的iN-1意义一致在插入排序中我们最后的endi要停留在倒数第二个元素是下标为N-2所以end才N-1才能取到N-2。所以们这里iN-gap也是为了确保end停留在倒数第二个元素上。
3第一个for循环
该for控制的是每组的元素gap为5数组被分成了5组j会每次都赋给end这样end的起始位置不同也就进行的组的更换再在第二个for中进行组内的排序
如图所示 gap为5的最终结果 然后gap就会变小进行新一轮的分组排序最后gap 1 的那一次的分组排序执行完就获得了一个有序的数组这就是希尔排序。
希尔排序还有另一种写法
//单for
void ShellSort(int* arr, int N)
{//gap初识为N元素的个数int gap N;//gap不为1就要继续的缩小并排序while (gap 1){//gap缩小gap gap / 2;for (int i 0; i N - gap; i){int end iint tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}arr[end gap] tmp;}}}}
第一种写法是分一组排序一组然后再去分一组再排序
第二种写法是多组并排也就是直接对数组选择性的进行排序
如图 end 1 就进行①的两个元素的排序以此类推
最后得到
‘ 然后再进行gap的缩小进行新一轮的排序 个人觉得双for循环的写法更加的易懂
五效果测试 六与插入函数的比较
相信很多人都并觉得希尔比插入好下面进行比较运算的时间单位ms来展示希尔的强大 测一万个随机数插入排序花了6ms希尔花了1ms 测十万个随机数插入排序花了0.6秒希尔花了9ms 测一百万个随机数插入排序花了63秒希尔花了0.1秒我就问你屌不屌
七一些容易出错的细节
1gap gap/2对于N比较大的时候不太够看建议gap gap/311是为了确保gap可以为1
2千万不要觉得end 的值 要经过 i 的复制感觉太过麻烦直接把end写在for循环那里这样会造成 end在for循环中改变自己大小控制不住
