二路归并排序(merge sort)
标签: 数据结构
学习人数: 5627

前言

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

 

算法思想

该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

动态效果示意图:

排序(7):归并排序

分而治之:

1、分阶段

排序(7):归并排序

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为logn。

2、治阶段
再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

排序(7):归并排序

排序(7):归并排序

 

代码实现

#include <std...
登录查看完整内容


课后作业

课后习题

 

【2012年真题】设有 6 个有序表 A、B、C、D、E、F,分别含有 10、35、40、50、60 和 200 个数据元素,各 表中元素按升序排列。要求通过 5 次两两合并,将 6 个表最终合并成 1 个升序表,并在最坏情况下比较 的总次数达到最小。请问答下列问题。 
1)给出完整的合并过程,并求出最坏情况下比较的总次数。 
2)根据你的合并过程,描述 N(N≥2)个不等长升序表的合并策略,并说明理由。 

参考答案:
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中Merge()函数;对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。 
1)对于长度分别为 m,n 的两个有序表的合并,最坏情况下是一直比较到两个表尾元素,比较次数为 m+n-1 次。故,最坏情况的比较次数依赖于表长,为了缩短总的比较次数,根据哈夫曼树(最佳归并树)思想的启发,可采用如图所示的合并顺序。 

根据上图中的哈夫曼树,6 个序列的合并过程为: 
第 1 次合并:表 A 与表 B 合并,生成含有 45 个元素的表 AB; 
第 2 次合并:表 AB 与表 C 合并,生成含有 85 个元素的表 ABC; 
第 3 次合并:表 D 与表 E 合并,生成含有 110 个元素的表 DE; 
第 4 次合并:表 ABC 与表 DE 合并,生成含有 195 个元素的表 ABCDE; 
第 5 次合并:表 ABCDE 与表 F 合并,生成含有 395 个元素的最终表。 
由上述分析可知,最坏情况下的比较次数为:第 1 次合并,最多比较次数=10+35-1=44;第 2 次合并,最多比较次数=45+40-1=84;第 3 次合并,最多比较次数=50+60-1=109;第 4 次合并,最多比较次数=85+110-1=194;第 5 次合并,最多比较次数=195+200-1=394。 
故,比较的总次数最多为:44+84+109+194+394=825 
2)各表的合并策略是:在对多个有序表进行两两合并时,若表长不同,则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想,依次选择最短的两个表进行合并,可以获得最坏情况下最佳的合并效率。 


登录后发布评论

暂无评论,来抢沙发