• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Shell Sort

AOJ 站点默认 6个月前 (04-04) 211次浏览 已收录 0个评论
文章目录[隐藏]

Question

FpUhq.png
Sample Input 1
5
5
1
4
3
2
Sample Output 1
2
4 1
3
1
2
3
4
5
Sample Input 2
3
3
2
1
Sample Output 2
1
1
3
1
2
3
0

Meaning

题目的要求是用希尔排序给一组数据排序,除了输出排列过后的数据。还需要输出增量序列以及排序次数。题目要求使用指定的增量序列,即1,4,13,40,121等等,该增量序列也是效率极高的一个,算法的时间复杂度维持在1.25。

Solution

如果理解了插入排序的话,这题应该不难。希尔排序就是给插入排序中的增量1换成指定的数,然后进行多次插入排序(当然最后肯定需要进行一次增量1的排序,以保证数据的有序性)。或许会疑惑,这样不是时间耗得更多 吗?,其实不然,因为插入排序法可以高速处理顺序比较整齐的数据,希尔排序就是充分发挥了这一特长的高速算法!还是回到解题步骤吧:在基础的插入排序函数中带入一个参数增量g,外层套一个增量序列G,每次给g=G[i]赋值,基础的插入排序算法中稍微修改一下就ok,给之前的加1,改成加g。

Coding

Summary


希尔排序,我在之前写代码时候在更改后的插入排序函数中原本是给i直接赋值给j,然后去判断a[j-1]和当前值tmp的大小,但是题目中前几个可以ac,后面就不可以了,喜欢深究的小伙伴可以告诉我这是为什么。
原来的:

修改后:

入坑笔记:大数组需要定义在main函数外面!


希尔排序和插入排序的比较:


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Shell Sort
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到