计算机二级辅导:合并排序计算机等级考试
文章作者 100test 发表时间 2010:01:01 13:04:07
来源 100Test.Com百考试题网
合并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。
有这样一组数据,{5,4,1,22,12,32,45,21},如果对它进行合并排序的话,首先将它从中间分开,这样,它就被分成了两个数组{5,4,1,22} {12,32,45,21}.
对这两个数组,也分别进行这样的操作,逐步的划分,直到不能再划分为止(每个子数组只剩下一个元素),这样,划分的过程就结束了。
划分的过程如下图所示:
接下来,我们进行合并操作,依照上图,划分过程是从上到下进行的,而合并的过程是从下往上进行的,例如上图中,最下层{5},{4}这两个数组,如果按升序排列,将他们合并后的数组就是{4,5}。{1},{22}这两个子数组合并后是{1,22}。而{4,5}与{1,22},这两个数组同属一个分支,他们也需要进行合并,由于这两个子数组本身就是有序的,所以合并的过程就是,每次从待合并的两个子数组中选取一个最小的元素,然后把这个元素放到合并后的数组中,前面两个数组合并后就是{1,4,5,22}。依次类推,直到合并到最上层结束,这是数据的排序已经完成了。
合并的过程如下图所示。这个过程是从下往上的。
C语言实现代码如下:
1#include