( ! ) 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
数学思维训练网 - 小学计算思维课程(18)-选择排序

小学计算思维课程(18)-选择排序

小学计算思维课程(18)-选择排序

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


第十八课:选择排序

在我们的生活中,大部份资料都是被排过序的,比如电话号码本一般按照音序来排列,一次数学考试按学号从低到高排列或者按成绩从高到低排列,音乐播放器列表中的音乐可以按加入时间来排序或者按歌曲名称来排序。排序有助于我们更快的找到我们想要的资料,比如“二分搜索”的前提条件是查找的对象必须是已经被排序的,排序还便于找到最高分和最低分。排序是如此重要,手工对成千上万的数据进行排序是非常麻烦的一件事,借助计算机我们可以在很短的时间内把大量数据排好顺序,今天我们就来学习其中的一种排序算法“选择排序”。

计算机和我们人类的工作方式有很大的不同,我们人类可以同时比较好几个数据,但计算机一次只能比较两个数据,比如在数列“10、50、2、30、8”中找到最小值,我们只要看一眼,就立刻知道最小的是2。而计算机不行,它一次只能对两个数字进行比较,为了理解计算机的排序原理,我们模拟计算机的运行方式。接下来的游戏中,我们将用一个方法让你看不到所有的数据,这样你一次就只能比较两个数据了。

准备:

1.托盘天平或自制玩具天平(如下图)

2.8个自制的物体,最好大小一样,如下图(里面可以装填不同数量的1角硬币或其它,并且在内部写上重量):

活动:

你可以在天平的帮助下,一次比较两个物体。依次找出最重的物体,从而实现从高到低的排列。

问题:

1.你一共比较了多少次才找到最重的物体?

2.如果需要在100个物体中找到最轻的,一共需要比较多少次?

3.需要比较多少次才能发现3个物体中最轻的一个?

4.如果有n个物体,找到最重的物体需要比较多少次?

5.8个物体排好顺序,一共需要比较多少次?能否用字母公式来表示?

像上面这样,先找出最重的物体并放在一边,然后在剩下的物体中再找出最重的物体,依次类推,直到全部物体被排好序。这样的排序方法被称为“选择排序”,因为你总是不断选择最大(或最小)的数。

衡量排序算法速度快慢的重要依据是“需要比较的次数”,对于选择排序法来说,如果有10个数据,第一次需要比较9次,第二次需要比较8次……,一共需要9+8+7+……+1=36次。如果有非常多的数据等待排序,那么它的运行将会非常缓慢,或许会让你等待1天之久。那么就请期待下面的课程给我们介绍更给力的算法吧!