一道归并排序题的解析

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/53710263

设有字母序列{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