极客小将

您现在的位置是:首页 » scratch编程资讯

资讯内容

用Scratch实现冒泡法排序—让你的鱼缸冒泡泡吧

极客小将2021-04-15-

upload/article/images/2021-04-15/b8e2f74dd9c73df9a7306ef261640d28.jpg

排序的方法有很多种,今天介绍一下“冒泡法”排序。

upload/article/images/2021-04-15/4334988a59a54477728e0b177e30f9e4.jpg

冒泡法排序的原理:对相邻的元素进行两两比较,顺序相反则进行交换。这样,每一次会将最小或最大的元素“浮”到顶端,最终达到完全有序。

具体可参见上面的图示。下面用Scratch进行实现。

程序实现:下图是排序算法部分。

upload/article/images/2021-04-15/8dad131cc89ee2404aec000d223b5234.jpg

本例只对5个小球进行排序,所以循环上限是5次。

其中,列表“序号”中存放了需要排序的内容。变量i是外循环计数,循环次数为5;变量j是内循环计数,循环次数是5-i。


难点一:为什么内循环的次数是5-i?

l  由于是两两进行比较,所以第一次比较时,只需要比较4次就可以了。而第一次运行时,外循环变量i=1,所以这时5-1=4;

l  第二次执行内循环时,由于最大的已经冒泡到顶部,只剩下4个元素。这4个元素,也只要比较3次就可以。而这时外循环变量i=2,刚好5-2=3。后面的依次类推。


难点二:如何引用数组结构中的元素?

在Scratch中没有提供“数组”这种数据结构,但是提供了“列表”。数组可以通过列表来实现。

例如,有数组A,它有5个元素。则每个元素分别为A(1)、A(2)、A(3)、A(4)和A(5)。有的编程语言数组的下标从0开始,有的从1开始。有的编程语言支持对数组的整体操作,有的只能一个元素一个元素的访问。

Scratch中只有列表,所以只能通过下标,一个个的访问。


 “交换”部分程序如下:

upload/article/images/2021-04-15/156a417ac14b833864aeb52bf66e555b.jpg

难点三:如何交换两个数据?

在程序中,两个变量必须通过第三个变量才能实现交换。因为在大部分编程语言中,等号的含义是“赋值”。

所以有的编程语言为了进行区分,将赋值号写成“:=”的形式。例如:

upload/article/images/2021-04-15/bc9c09adbc8009152239dffd5af422c2.jpg

其含义是将100这个值赋予变量a。

因此直接写成下列形式,是不能交换变量a和b的值的:

upload/article/images/2021-04-15/730f13b32e9097e9431fa37c6663b9c5.jpg

执行第一条语句时,将变量b的值赋予了变量a,这时变量a的值已经等于变量b了。所以执行第二条语句时,只是再一次把值赋予变量b。变量a的值丢失了。

通常采用中间变量来实现交换。例如:

upload/article/images/2021-04-15/9370375687f0bf21f8b11779d36db7d2.jpg

这里temp就是中间变量。注意其中的次序不能搞错。


完整的视频如下所示:


后记:在利用冒泡法排序时,如果某次循环中没有发生交换,说明所有数据都已经排好了顺序。这时可以中止循环,直接宣布排序结束。通常的做法是设置一个标志变量flag。开始时设置flag=0;当可以提前中止时,设置flag=1。Scratch语言中没有break等中断循环的命令,一般是设置一个快速变量。这样条件判断部分就变得稍微复杂一些。

下面是跟算法无关的一些内容,只是为了让程序更有趣:

1、按住“R”键可以重置需要排序的序列。新的序列是随机生成的。再次按“空格”键可以开始排序;

2、设计了一条小鱼可以提供各种信息,例如“排序结束”等。为了让我们的泡泡鱼缸更生动形象,小鱼会在鱼缸中“漫步”。

3、为了更直观的展示排序过程,对5个小球进行了编号。编号可以去掉,排序的泡泡也可以换成你希望的物品哦。

声明:本文章由网友投稿作为教育分享用途,如有侵权原作者可通过邮件及时和我们联系删除

网友点评

共有5条评论来说两句吧...