Scratch选择排序-玩扑克学算法系列之二

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

什么是选择排序?

选择排序(Selection sort)是一种简单直观的排序算法。其基本思想是:

首先在未排序的数列中找到最小(或者最大)元素,然后将其存放到数列的起始位置;接着,再从剩余未排序的元素中继续寻找最小(或者最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

其排序方式可以参考下图:

选择排序动图效果
选择排序动图效果

选择排序过程

会打扑克就会选择排序,选择排序很像我们打扑克牌时,把牌从左到右扫描,找到最小的一张牌,放到最左边,然后从第二张牌继续扫描第二小的牌,放到第二的位置,以此类推,直至所有的牌都排列好,这个画面感是不是很熟悉,其实这就是选择排序。

扑克牌
扑克牌

为了更好的理解选择排序,下面介绍如何使用扑克牌来演示详细的排序过程。

准备扑克牌一副,红蓝色棋子各一枚,为便于演示,取牌面为2、5、6、7、9的5张纸牌进行排序操作。将5张纸牌打乱顺序,假定牌面从左到右依次为7、9、5、2、6。由于每次都需要挨个比较找到最小的纸牌,因此5张牌需要进行4轮排序。

第1轮排序:将红色和蓝色棋子放在左边第1张纸牌上方,标记为j,然后从红色棋子所在位置的下一张纸牌(j+1)开始,从左至右依次把每一张纸牌与蓝色棋子所在位置的纸牌进行比较,并将蓝色棋子放置在较小的纸牌上方。直到将红色棋子右边的纸牌全部比较一遍,此时蓝色棋子就停留在最小的纸牌上方。然后将红色棋子和蓝色棋子所在位置的两张纸牌交换位置,至此完成第一轮排序,最小的一张纸牌2被移到正确位置,如图:

第1轮排序过程图示
第1轮排序过程图示

第2轮排序:将红色棋子和蓝色棋子放置于左边第2张纸牌上方(j=2),按照上述步骤进行比较,然后交换位置,在第二轮排序完成之后,纸牌5就移到了正确位置,如图:

第2轮排序过程图示
第2轮排序过程图示

第3轮排序:再将红色和蓝色两枚棋子置于左边第3张纸牌上方(j=3),重复上述过程,对纸牌进行比较和交换,完成第三轮排序后,纸牌6就移到了正确位置,如图:

第3轮排序过程图示
第3轮排序过程图示

第4轮排序:继续移动棋子,将它们放到左边第4张纸牌上方(j=4),继续前面的步骤,在第四轮排序完成之后,纸牌7就处于正确的位置,而剩下的纸牌9自然而然也就处于正确位置了,如图:

第4轮排序过程图示
第4轮排序过程图示

至此,整个排序过程结束,这是5张扑克牌已经按照从小到大排好序了,依次为2,5,6,7,9。

编程思路

根据上述过程分析,在排序过程中,这里的红色棋子和蓝色棋子是用来进行标记的,可以使用变量来表示,而每一轮排序都需要交换位置,因此需要定义一个自制积木来实现数字的交换。

代码实现

1.创建并初始化列表

建立一个“纸牌”列表,清空列表,并将纸牌数字7、9、5、2、6依次加入列表,编写代码如下:

建立列表并初始化
建立列表并初始化

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

创建自制积木,用于对列表中的数据进行交换,需要定义两个参数,不过参数不是纸牌本身,而是纸牌对应的编号,编写程序如下:

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

3.创建“选择排序”自制积木

再建立一个自制积木用于排序,根据上面的排序过程描述,在排序过程中需要设置两个标记,这个可以使用变量来实现,建立两个变量“a”和“b”,同时还需要单独再再利用循环进行多轮排序,具体的代码如下:

建立“旋转排序”自制积木
建立“选择排序”自制积木

4.调用自制积木完成排序

接下来,就可以调用自制积木进行排序了,如图:

调用自制积木进行排序
调用自制积木进行排序

程序效果

程序执行的效果如下:

选择排序执行效果
选择排序执行效果

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

昵称

取消
昵称表情代码图片