一道归并排序题的解析

设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并方法对该序列进行一趟扫描后的结果为 ()。


二路归并:如果序列中有n 个记录,可以先把它看成n个子序列,每个子序列中只包含一个记录,因而都是排好序的。二路归并排序先将每相邻的两个子序列合并,得到n/2(向上取整)个较大的有序子序列,每个子序列包含2个记录。再将这些子序列两两合并。如此反复,直到最后合并成一个有序序列,排序即告完成。

设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1};

第二次归并后:{6,100,202,301},{1,8,38};

第三次归并后:{1,6,8,38,100,202,301}

对于本题,初始数列为:{Q,D,F,X,A,P,N,B,Y,M,C,W}

初始状态:Q,D,F,X,A,P,N,B,Y,M,C,W

第一次归并后:{D,Q},{F,X},{A,P},{B,N},{M,Y},{C,W};

第二次归并后:{D,F,Q,X},{A,B,N,P},{C,M,Y,W};

第三次归并后:{A,B,D,F,N,P,Q,X},{C,M,Y,W};

第四次归并后:{A,B,C,D,F,M,N,P,Q,X,Y,W};


参考答案 :DQFXAPBNMYCW

上一篇:Centos7基于Docker搭建ELK日志收集分析系统


下一篇:Centos下利用shell脚本监控和重启进程.并邮件通知