无论学习哪一种编程语言，进行算法方面的训练时都绕不开“排序”。排序在进阶编程中有非常广泛的应用，要想成为编程高手，排序算法是必备要掌握的。由于这部分内容相比以前我们学过的算法更加抽象、不容易理解。因此，我们把它放在进阶篇的最后，依次给大家讲解以下四种排序算法：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
完成四种排序算法的学习之后，我们还会做一个综合的排序算法大比拼，直观体验一下不同排序算法优劣。
你准备好挑战Scratch编程的最后难题了吗？让我们开始吧！
问题
使用冒泡排序算法对列表中随机生成的10个数据进行从小到大排序，即最小的数字在最上面，最大的数字在最下面。
分析
冒泡排序也称为“起泡排序”，是一种简单的排序算法。它的排序思想是重复地“走”过要排序的数字列表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复这个过程直到没有再需要交换的元素为止。
我们用生活中常见的排队场景来解释它：
老师要对五位同学按身高排队，个子最高的站后面（右边），最低的站前面（左边），这五位同学分别是明明、欢欢、乐乐、格格和图图。他们五个人的身高是这样的：
老师首先站到队伍最后面（这里用蜻蜓代表老师的位置，他会比较最后一位同学（图图）和他前一位同学（格格）的身高，发现格格低一点，按照要求，身高低的在最前面，所以是不用换位置的，于是他直接走到了第二位同学格格的位置。
现在老师仍然按照刚才的方法，比较格格与前一位同学的身高，发现乐乐要高一点，这不符合排队要求，所以他要求格格和乐乐换位置，然后他走到第三位同学的位置（由于格格和乐乐换了位置，所以第三个位置还是格格）：
现在老师拿格格与前面的可可比身高，发现可可还是高一点，于是要求他们交换，老师跟着走到了第二个位置（还是格格）：
老师拿格格与他前面一位同学欢欢比较，显然，需要交换位置。换完老师也走到了队伍的第一位：
老师发现，这时候前面已经没有同学可以比较了，所以老师在格格的位置做个标记，表示格格这个位置（第一个位置）已经排好了，下一轮再排队就不用再考虑她了。然后老师回到队尾，开始第二轮：
你有没有发现，经过这一轮，身高最小的格格已经站到了第一位？也就是格格已经站到了她应该在的位置，“已经排好队”了。这就像小鱼吐泡泡一样，比较轻的气泡在水中会上浮，格格作为最“轻”（也就是身高最低）的同学，已经“浮”上来了——这就是“冒泡”排序的由来。
下面老师再进行第二轮排序的逻辑和刚才是一样的，这里我就不一一描述了，你可以自己看一下图，是不是和自己的理解一样：
可以发现，经过第二轮比较，身高第二低的同学乐乐“冒泡”到了第二个位置，他的位置也定好了，第三轮就不再考虑他了。
老师的工作仍然没完成，他继续回到排尾工作：
第三轮完成了，可可已经站到合适的位置。
第四轮完成，图图“冒泡”成功。
最后一轮，老师发现，除了欢欢这个大个子，其它同学都排好队了，他也不用跟别人比了。于是，排队结束，老师长长地松了一口气。
现在我们再要概括一下上面冒泡排序的过程： – 从队尾（列表的元素数）开始比较相邻的元素。如果元素比前面的元素小，就交换它们两个； – 对每一对相邻元素作同样的工作，从队尾第一对到队首的最后一对，这样会把这一轮最小的元素排到最前面； – 重复上面的步骤，直到排序完成。
编程
一、我们新建Scratch项目后，首先建立一个列表“数组”，用于保存要排序的数字。然后添加一个自制积木，用于交换列表中两个元素的位置。为什么要编写这样一个自制积木呢？因为我们在排序过程中要根据需要交换列表中元素的位置，但无法直接调用一条指令让列表中两个元素位置互换，所以就借助一个临时变量temp来完成交换过程。这就像我们左手和右手各拿了一个大苹果，要把这两个苹果交换，我只能先把其中一只手的苹果先放到桌子上（保存到临时变量），然后把另一只手的苹果拿过来，空下来的手再去桌子上拿剩下的苹果一样。这是一个很有用的模块，以后我们写其它排序算法的时候也要调用，所以应该熟悉它。
二、编写指令，在启动程序时生成10个随机数字加入数组，调用一个自制积木“冒泡排序”来排序。这里我们用了i和j两个变量，其中j代表的是第几轮比较，有几个元素就要比较几轮（回顾刚才我们排队的过程），所以它从1开始，每比较一轮加一，直至等于数组项目数为止，这时候就代表完成了全部比较；i变量则代表的是当前比较的位置，每轮开始的时候都从队伍尾部（也就是列表的最后一个元素）开始比较，所以i先设置为数组的项目数，每次比较都让第i个元素和它前面的元素（第i-1个元素）比较，如果发现小于前面的项，就把位置换过来，然后把i减一（相当于老师前进一步）。走到了i=j，也就是当前已经排好的同学位置的时候就不比了，继续下一轮。如此直至j=列表项目数，只剩下最后一位同学自己了，不再比较，排序完成。
三、你可以把程序中加上暂停，观察冒泡排序过程中数据是怎么一步一步变化的。完全理解之后，我们再对“冒泡排序”自制积木进行一点改进：
我们增加了一个变量swap，用它表示在每一轮比较过程中是否发生过交换位置的情况。在每轮开始的时候，把它设置为0，代表False（假），没有发生比较的意思。在比较过程中如果发生了交换位置，把它设置为1，也就是True（真），表示这一轮发生过比较。这样有什么用呢？大家想想，老师从队尾向前走的时候，发现没有同学需要和前面的同学换位置，这说明同学们已经按照要求站到了合适的位置上，排序已经完成了，那就退出排序，提前结束，不是节约时间了吗？
四、程序完成。
总结
第一种排序算法完成了，感觉是不是挺简单的？冒泡排序确实是很容易理解的排序算法，但它的效率不太高。大家算一下如果不考虑提前结束的情况，我们比较了多少次完成：
- 第一轮：要拿一位同学和其它四位同学比较，4次；
- 第二轮：有一位同学已经排好了，所以要比较3次；
- 第三轮：2次；
- 第四轮：1次；
最后只剩下一位同学就不比较了，总共比较了 4+3+2+1 =10次。
如果列表中的数据非常多，我们要比较的次数也会很多，这就要消耗比较长的时间来完成排序过程。等下面完成其它排序算法的学习之后，我们再来讨论它们之间的优劣吧。
