Scratch快速排序-玩扑克学算法系列之五

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

什么是快速排序

快速排序是对冒泡排序的一种改进,它是由东尼·霍尔在1962年提出的一种划分交换排序,采用的是分治策略(一般与递归结合使用),以减少排序过程中的比较次数,快速排序被认为是当前最优秀的一种内部排序算法,它的基本思想是:

选择未排序数组左端的第一个元素作为基准,经过一轮排序后,小于基准的元素移到基准左边,而大于基准的元素移到基准右边,而作为基准的元素移到排序后的正确位置。这样整个数组被基准划分为两个未排序的分区。之后依次对未排序的分区以递归方式进行上述操作。每一轮排序都能使一个基准元素放到排序后的正确位置。当所有分区不能再继续划分,排序完成,就得到一个升序排列的有序数组。

快速排序示意图
快速排序示意图

快速排序过程详解

为了让你更好的理解快速排序,下面将介绍如何使用扑克牌来演示快速排序算法。

准备好扑克牌一副,红、蓝色棋子各一枚,为便于演示,取牌面为2、4、6、7、8的5张纸牌进行排序操作。将5张纸牌顺序打乱,假定5张牌从左到右依次为7、6、8、2、4。

第一轮排序:开始时5张纸牌都未排序,在左右两端的第1张牌和第5张牌上方各放置一枚红色和蓝色棋子,以红色棋子出的第一张纸牌7作为基准,然后先从右到左移动蓝色棋子,将它停留在找到的第一张小于基准的纸牌4上方;再从左向右移动红色棋子,将它停留在找到的第一张大于基准牌的纸牌8上方。这时红蓝两枚棋子没有碰到一起,将它们下方的两张纸牌8和4交换位置。

按这个方法继续移动蓝色和红色棋子,它们都停留在纸牌2的上方,这时两枚棋子碰到一起,将纸牌2和7交换位置,至此,基准纸牌7就移到了正确的位置,而整个未排序的纸牌被基准纸牌7划分为两个未排序的分区,排序过程如图所示:

快速排序第一轮排序过程
快速排序第一轮排序过程

第二轮排序:在第1张和第3张纸牌上方分别各放置红色和蓝色棋子,将第1张纸牌2作为基准,然后按照上面描述的方法移动两个棋子,它们都停留在纸牌2的上方。这时基准牌位置和两枚棋子相遇的位置相同,不需要处理,基准纸牌2已经处于正确位置,如图所示:

快速排序第二轮排序过程
快速排序第二轮排序过程

第三轮排序:在第2张第3张纸牌上方分别放置红色和蓝色棋子,将第2张纸牌6作为基准,然后按照前面描述的方法移动两枚棋子,它们相遇在纸牌4上方,这时将纸牌6和纸牌4交换位置,至此,基准纸牌6就被移到了正确的位置,如图:

快速排序第三轮排序过程
快速排序第三轮排序过程

最后就剩下第2张和第5张纸牌这两个未排序的分区,由于这两个分区都只有一张纸牌,不需要继续分区,因此它们已经处于正确位置了,因此,整个快速排序过程也就结束了,5张纸牌已经按照从小到大的顺序排列好了。

编程思路

根据快速排序的基本思想,对于一个未排序数组,每一轮排序都需要先确定基准点,并寻找分区点,在寻找分区点的过程中,需要将右侧小于基准点的数字和左侧大于基准点的纸牌进行交换,一旦找到分区点,则将基准点的纸牌和分区点的纸牌进行交换,然后分别对左边和右边的分区重复这个过程即可。

因此,我们需要依次解决如下3个问题:

  • 交换指定位置的纸牌
  • 寻找分区点
  • 递归调用

程序实现

1.定义“交换位置”自制积木

根据编程思路的分析,先来解决第一个问题,即交换指定位置的纸牌,可以定义第一个自制积木,如下:

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

2.定义“寻找分区点”自制积木

接着,就可以定义“寻找分区点”自制积木了, 代码如下:

定义“寻找分区点”自制积木
定义“寻找分区点”自制积木

3.定义“快速排序”自制积木

由于需要用到递归,这里必须要定义一个“快速排序”自制积木,然后在自制积木中再次调用自己,具体的代码如图所示:

定义“快速排序”自制积木
定义“快速排序”自制积木

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

有了快速排序自制积木,就可以直接对纸牌数组进行排序了,在绿旗指令下添加代码如下:

调用自制积木完成快速排序
调用自制积木完成快速排序

作品效果

Scratch快速排序的执行效果如下图所示:

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

昵称

取消
昵称表情代码图片