起航学习网

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

冒泡法排序的原理是什么 如何用scratch使鱼缸冒泡泡

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

冒泡法排序的原理是什么 如何用scratch使鱼缸冒泡泡

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

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

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

冒泡法排序的原理是什么 如何用scratch使鱼缸冒泡泡

本例只对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中只有列表，所以只能通过下标，一个个的访问。

“交换”部分程序如下：

冒泡法排序的原理是什么 如何用scratch使鱼缸冒泡泡

难点三：如何交换两个数据？

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

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

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

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

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

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

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

完整的视频如下所示：

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

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

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

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

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

文章出自：http://qh.itpxw.cn/peixun/software/201949092.html

文章标题：冒泡法排序的原理是什么 如何用scratch使鱼缸冒泡泡

免责声明：本站文章均由入驻起航学习网的会员所发或者网络转载，所述观点仅代表作者本人，不代表起航学习网立场。如有侵权或者其他问题，请联系举报，必删。侵权投诉