https://y.music.163.com/m/song/18860373
那么,我开始介绍归并排序(Mergesort),包括其算法的运作机制,原理,具体实现,改进方案,复杂度与缺点。
首先,为了普适性,我们拿的例子是一个仅包含数字的列表:[1.0, 3.1, 2.5, 5.6, 0.7]。
“[”代表列表的开始,“]”代表其结束,其中每一个被逗号分割的数字都是一个该列表的元素。
归并排序的运行机制如下:
将列表从中间切开,分成两个列表[1.0, 3.1]与[2.5, 5.6, 0.7](如果为奇数,我们在这里默认切成(n-1)/2和(n+1)/2的长度,反过来也不会有什么影响)。
为了方便表示,我们写作[1.0, 3.1/2.5, 5.6, 0.7]表示我们在“/”的地方切了一次,分成了两份。
对每个切开后的列表再次切开,例如[1.0, 3.1]将变为[1.0]和[3.1](注意,[1.0]并不是1.0,前者是含一个元素的列表,后者是一个数字)。
像这样,每次一切为二,在经过三次切割后可得[1.0/3.1/2.5/5.6/0.7]。
这是归并排序的第一步,分开。对于长度为n(含n个元素)的列表,需要花费的时间为lg(n),其中lg为以2为底的log(不知道什么是log?请自行学习对数)。
分久必合,下一步是合。
在最后一次切割结束后,对于每一轮切割过后的两半,将这两半合起来,以一个保证其从小到大排列的方式。
什么意思?我们还是看刚才的例子。
在最后一轮中,[5.6, 0.7]被拆分为[5.6],[0.7]。现在我们想以从大到小排列的顺序来合并这两个数,方法很简单:比较一次5.6,0.7的大小。0.7小,所以0.7排前面,5.6排后面,两个列表合并为[0.7,5.6]。
在倒数第二轮(也就是第二轮)中,[2.5]和[5.6, 0.7]被拆分开来。因为我们已经将[5.6, 0.7]在拆分后有序组合,使其变为[0.7, 5.6],我们需要让2.5先和[0.7, 5.6]中的第一个数0.7比,比0.7大之后再和5.6比。比5.6小,则排5.6前面,变为[0.7, 2.5, 5.6]。
同理,[1.0, 3.1]和[0.7, 2.5, 5.6]比。1.0大于0.7小于2.5,则排在两者之间。3.1因为在1.0后,而0.7小于1.0,所以3.1必定大于0.7,从2.5开始比。比2.5大,比5.6小,所以排两者之间。
列表被排序完成。
被排序的列表带来了秩序。秩序的作用会在下文中提到,在其原理之后,在具体实现之前,但是我们可以先听听Disorder,感受一下无序是多么痛苦的一件事吧。