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

小学计算思维课程(21)-归并排序

小学计算思维课程(21)-归并排序

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


第二十一课:归并排序

归并排序是另一个使用“分而治之”原理的排序算法。首先将待排序对象随机分成两组(两组对象数量相等或差一个),然后分别对两组对象进行排序,再将两组对象归并起来。归并两个已经排好序的序列很容易,你只要不断地移出两组对象最前面较小的那个即可。比如下图中:

40和60位于前面,通过比较选出较小数40并入前面序列。现在50和60位于前面,通过比较选出较小数50并入前面序列……

那么,怎样对刚才的子序列进行排序呢?方法和刚才一模一样,还是用归并排序法。这样不断的分裂,直到子序列中只剩下一个对象,然后不断的合并这些子序列。完成后就得到了排序后的序列。下面我们用一个活动来理解归并排序算法。

准备:

8个大小相同但重量不同的物体,一架天平。

活动:

使用“归并排序”算法进行排序,并记录比较次数。

问题:

1.使用归并排序算法对8个物体进行排序,一共比较了几次?

2.你认为上面学的5种排序算法中,那种方法速度最快?

3.当你将两个各含有4个对象的序列合并时,最多需要比较多少次?

4.当你将两个各含有4个对象的序列合并时,最少需要比较多少次?

快速排序和归并排序的效率可以说不相上下,但因为原理不同,其中快速排序需要经常移动数据的位置,而归并排序经常要合并数据。所以在计算机中它们的使用是有侧重的。快速排序适合对计算机内存中的数据进行排序,归并排序更适合处理存储在硬盘上的数据。

从前面的介绍中我们可以发现,快速排序和归并排序的比较次数和分裂的次数有关。如果有8个对象,第一次分成2个4,第二次分成2个2,第三次分成2个1,这时分裂完成。即每次对象的数量除以2,一直除到序列中对象数量为1。在数学上,这样的计算用log2n表示,如log28=3。经过测算,快速排序平均比较次数为1.39nlog2n次,归并排序只需要nlog2n次。也就是说归并排序比快速排序快39%。但因为归并排序需要大量的临时空间,所以一般来说快速排序才是最佳选择。

在美国2008年大选时,Google采访了总统候选人“奥巴马”,当奥巴马被问到“对一百万个数进行排序的最佳方法”时,他回答道“冒泡排序绝对不是正确答案”。这个答案相当巧妙,赢得了听众的一致好评。如果采用冒泡法,将需要比较499999500000次,而快速排序法只需要比较20000000次,它的速度是冒泡法的25000倍。

虽然并不是每个人都会成为计算机科学家,但在计算机大规模应用于工作生活中的二十一世纪。学习一点计算思维的知识并理解计算机的工作原理,对于我们的工作和学习会起到很大的帮助。