( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230624{main}( ).../view.php:0
20.0001231368include( '/var/www/html/head.php' ).../view.php:2
30.0009250728isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(20)-快速排序

小学计算思维课程(20)-快速排序

小学计算思维课程(20)-快速排序

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com


第二十课:快速排序

虽然选择排序、插入排序和冒泡排序算法很简单,但它们效率很低,在实际生产中对大量数据进行排序一般使用“快速排序”或“归并排序”。这节课我们来学习快速排序算法。下面我们以一个活动来理解它的排序原理。

准备:

1.8个大小相同且重量不同的物体。

2.一架天平。

活动:

1.任意选取一个物体,将其它物体依次和它进行比较,较重的放左边,较轻的放右边(将所有重物分为两组)。如下图所示:

2.对左右两组物体再次运用刚才的方法进行分组,直到组内物体个数为1个或0个。

问题:

1.使用快速排序法排列8个物体,你一共比较了多少次?

2.与前面的排序算法比较,是少了还是多了?

3.与其它同学的结果进行比较,是少了还是多了?你认为是什么原因造成的?

在活动中,一开始被选出的物体,我们称它为“基准”,比如例子中的基准是“50”,它差不多位于序列的中间,但我们在排序时,并不能保证一定选中这样的物体,最坏的时候甚至于左边的数量为0。

快速排序最妙的是,我们在第一步把对象分为左右两组后,还可以用同样的方法对这两组进行排序,这样不断“分裂”直到排序完成。这样的过程计算机科学中称为“递归”,即不断用相同的方法将序列划分为越来越小的各部分,并采用相同的步骤对各部分排序,这种方法还可以叫“分而治之”。因为物体太多不容易排序,那么就把它们分割直到只剩下一个物体,而一个物体的排序是最简单的。

问题:

1.快速排序是否“快速”取决于你是否选对了“基准”对象,你认为怎样的基准是好的?

2.好的基准在排序中起了什么作用?在8个物体的情况下,好基准和坏基准的比较次数相差多少?

3.如果有20个物体,如果每次都选了好基准,需要多少次比较可以排序完成?