Scratch插入排序-玩扑克学算法系列之三

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

什么是插入排序?

插入排序是一种简单的排序算法,也称之为直接插入排序,它的基本思想是:

把一个要排序的数组划分为已排序和未排序两部分,再从未排序部分逐个取出元素,把它和已排序部分的元素进行比较,从右到左比较相邻的两个元素,如果右边的元素比左边的元素小,则交换两个元素,并向左继续比较和交换,否则就停止比较。按此处理未排序部分的所有元素,最终得到一个按升序排列的有序数组。

其过程如图所示:

插入排序动图演示
插入排序动图演示

插入排序很像大部分人玩扑克牌时的操作,从第二张牌开始,跟第一张牌比较, 如果比第一张牌小,那么就插入到第一张前面,这样两张牌就是排好序的,然后再把第三张牌跟前面排好序的两张牌做比较,插入到已经排好序的两张牌里面,这样就形成了三张排好序的牌,,后面的牌一次就行插入排序操作。这种打牌排序方式才是大多数的选择,前面选择排序的方式可能只有极小部分与众不同的人会那么操作。

图片[2]-Scratch插入排序_打扑克学算法编程系列-51scratch少儿编程
扑克牌的插入排序

插入排序过程详解

下面介绍如何使用扑克牌演示插入排序算法,准备扑克牌一副,红、蓝色棋子各一枚,为便于演示,取牌面为2、4、6、7、8的5张纸牌进行排序操作。将5张纸牌打乱顺序,假定5张牌从左到右一次为6、4、8、2、7。

先把左边的第1张纸牌翻开,作为已排序部分,其他纸牌作为未排序部分。对于5张牌,我们需要使用经过4轮排序。

第一轮排序:将红色棋子(标记为j)和蓝色棋子(标记为i)放在第2张纸牌处,再将纸牌4与左边的纸牌6进行比较,将较小的纸牌4与纸牌6交换位置,将蓝色棋子向左移动一步,这是i=1,结束第一轮排序,纸牌4处于正确位置,如图:

插入排序第一轮排序
插入排序第一轮排序

第二轮排序:将红色和蓝色棋子右移一步放在第3张纸牌上方(j = j + 1),再将纸牌8与左边的纸牌6比较大小,它比纸牌6大而无需交换,结束第2轮排序,纸牌8处于正确位置,如图:

插入排序第二轮排序
插入排序第二轮排序

第三轮排序:将红色和蓝色棋子右移一步,放在第4张纸牌上方(j = j + 1),再将纸牌2与左边的纸牌8进行比较,将较小的纸牌2与纸牌8交换位置,将蓝色棋子左移一步,再与纸牌6比较大小,交换位置,继续左移蓝色棋子,与纸牌4进行比较,需要交换位置,左移蓝色棋子,此时已经到左边了,结束第三轮排序,纸牌2已经处于正确位置了,如图:

插入排序第三轮排序
插入排序第三轮排序

第四轮排序:将红色和蓝色棋子右移一步放置于第5张纸牌上面(j = j + 1),再将纸牌7与左边的纸牌8比较大小,将较小的纸牌7与纸牌8交换位置,左移蓝色棋子,将纸牌7余纸牌6比较大小,它比纸牌6大无需交换,这时结束第四轮排序,纸牌7已处于正确的位置上了,如图:

插入排序第四轮排序
插入排序第四轮排序

至此,整个排序过程结束,这时5张扑克牌已经按照从小到大的顺序排列完毕。

编程思路

根据上面的过程描述,首先需要定义一个交换两个数组元素的自制积木,用于交换纸牌,然后就可以调用自制积木来进行排序了,排序的时候,从第2个元素开始处理,每一轮只处理一个元素,把当前需要的处理插入到正确位置即可。

程序实现

1. 定义“交换元素”自制积木

建立自制积木,命名为交换元素,需要两个参数a和b,表示列表元素的下标,temp则是临时保存数据的变量,代码如下:

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

2. 定义“插入排序”自制积木

接下来,再建立一个自制积木,命名为“插入排序”,再结合双重循环,完成排序,对应的代码如下:

“插入排序”自制积木
“插入排序”自制积木

3. 对纸牌进行插入排序

仍然遵循IPO的设计原则,先输入数据,调用自制积木进行处理,然后输出结果,编写代码如下:

调用自制积木完成插入排序
调用自制积木完成插入排序

作品效果

运行程序,其完整的效果如图所示:

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

昵称

取消
昵称表情代码图片