Scratch希尔排序-玩扑克学算法系列之四

Scratch希尔排序-51scratch
Scratch希尔排序-玩扑克学算法系列之四
此内容为付费资源,请付费后查看
9.9
限时特惠
19.9
立即购买
您当前未登录!建议登陆后购买,可保存购买订单
付费资源

什么是希尔排序?

希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。其基本思想是:

先将整个待排序元素序列分割成若干子系列(由相隔某个增量的元素组成)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序时,再对全体匀速进行一次直接插入排序。

希尔排序过程详解

下面介绍使用扑克牌来演示希尔排序算法的详细过程。

准备扑克牌一副,红蓝色棋子各一枚,为便于演示,取牌面为1、5、6、7、9的5张纸牌进行排序操作。将5张牌打乱顺序,假定5张牌从左到右依次为6、7、9、1、5。对于5张纸牌,经过3轮排序即可完成。

第一轮排序:先计算间隔,用5除以2再四舍五入,gap = 5 / 2 = 3,以3为间隔放置两枚棋子,将红色棋子放在第1张纸牌上方,将蓝色棋子放在第4张纸牌上方。接着比较两张纸牌,纸牌1小于纸牌6,将两者交换位置。之后将两枚棋子分别向右移动一步,纸牌5小于纸牌7,将两者交换位置,到此第一轮排序结束,如图:

希尔排序第一轮排序
希尔排序第一轮排序

第二轮排序:缩小间隔,gap = gap / 2,即 3 / 2 = 1.5,四舍五入为2,以2为间隔放置两枚棋子,将红色棋子放在第1张纸牌上方,将蓝色棋子放在第3张牌上方。接着比较两张纸牌大小,纸牌1小于纸牌9,不用交换。再将两枚棋子分别右移一步,纸牌6大于纸牌5,不用交换。继续右移两枚棋子,纸牌7小于纸牌9,将两者进行位置交换,到此,结束第二轮排序,如图“

希尔排序第二轮排序
希尔排序第二轮排序

第三轮排序:继续缩小间隔,gap = 2 / 2 = 1,以1为间隔放置两枚棋子,将红色棋子放在第1张牌上方,蓝色棋子放在第2张牌上方,接着比较两处的纸牌,纸牌1小于纸牌5,不用交换。向右移动两枚棋子,进行比较,纸牌5小于纸牌7,无需交换。再分别将两枚棋子向右移动一步,纸牌6小于纸牌7,两者交换位置。继续右移棋子,纸牌7小于纸牌9,不用交换,至此第三轮排序结束,如图:

希尔排序第三轮排序
希尔排序第三轮排序

当间隔为1的排序过程结束后,5张纸牌已经按照从小到大的顺序排列完毕。

编程思路

依然遵循IPO设计原则,输入一个无序的列表,经过排序处理,再输出已排序的列表。重点是排序处理,不变的仍然是交换元素操作,所以还是要先定义好交换元素的自制积木,然后再定义一个自制积木,结合双重循环来完成排序。

程序实现

1. 建立“交换元素”自制积木

创建自制积木,将其命名为“交换元素”,代码如下:

“交换元素”自制积木
“交换元素”自制积木

2. 建立“希尔排序”自制积木

创建自制积木,并命名为“希尔排序”,具体的代码如下:

“希尔排序”自制积木
“希尔排序”自制积木

3. 完成排序

接下来,我们就可以准备好列表数据,使用“希尔排序”自制积木完成排序,具体的代码如下:

使用“希尔排序”自制积木完成排序
使用“希尔排序”自制积木完成排序

作品效果

Scratch希尔排序的执行效果如图所示:

Scratch希尔排序效果演示
Scratch希尔排序效果演示
© 版权声明
THE END
喜欢就支持一下吧
点赞12赞赏 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片