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