( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230192{main}( ).../view.php:0
20.0001230936include( '/var/www/html/head.php' ).../view.php:2
30.0009250296isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(19)-插入排序和冒泡排序

小学计算思维课程(19)-插入排序和冒泡排序

小学计算思维课程(19)-插入排序和冒泡排序

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


第十九课:插入排序和冒泡排序

插入排序和我们平时玩扑克牌时的理牌原理差不多,看下图:

即每次拿到扑克牌,都按大小插入到扑克牌队列中,最后我们总可以得到排好序后的扑克牌。下面请你用上节课的道具,将8个物体用插入排序法按从重到轻进行排序。并记录下你一共比较了多少次。

总的来说,插入排序比选择排序快一点点,平均下来你只要将每个物体与半数进行比较即可。当然这只是一个平均值,运气好的时候会少一些,运气差的时候会多一些。但它仍然是一个很慢的方法,如果采用插入排序对1000个对象进行排序需要比较25万次。

问题:

1.如果碰巧你每次选取的物体都是最轻的一个,那么8个物体进行排序一共需要比较多少次?

2.如果碰巧你每次选取的物体者是最重的一个,那么8个物体进行排序一共需要比较多少次?

插入排序和选择排序都是非常容易理解的算法,下面介绍的“冒泡排序”就相对难一些。它的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。比如我们要从小到大排列以下5个数字:65、54、12、53、4。它的过程如下:

上面的图示演示了“第一趟”比较的过程,先比较65和54,因为65>54不符合要求,所以交换它们的位置,再比较65和12,同样不符合要求,再交换位置,一直比较到队列结束。我们可以看到数列中最大的数65就像一个“汽泡”一样已经冒出了水面。而“第二趟”就只需要比较前面的4个数,依次类推就可以把数列按从小到大排好。

活动:

使用上面的材料,运用冒泡排序法对它们进行排序,并记录比较的次数。

问题:

1.8个物体运用冒泡排序法一共需要比较几次?

2.上面介绍的三种排序算法,哪种算法需要比较的次数最少?

3.如果要对21个物体进行排序,在最坏的情况下,这三种算法需要进行多少次比较才能完成排序?

到止为止,我们一共学了3种排序算法,虽然三种排序算法需要的平均比较次数各不相同,但它们在最坏情况下需要比较的次数都是1+2+3+…+(n-1),这是一个等差数列,它们的和等于n×(n-1)÷2,当n非常大时,结果约等于n2÷2。正是这个原因,这三种排序算法被称为“n2”排序法,或称为二次排序法。二次排序法的速度相当慢。当数据非常多时,更是慢如蜗牛!接下来学习的排序算法则不会被n2影响,它们的速度会快的多。