设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W_腾讯笔试题

推荐

十年后的机器猫

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

编辑于 2015-02-09 17:38:11 回复(11)

谷哥的小弟

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

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

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

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

QDFXAPNBYMCW归并扫描第一遍：两两归并，即{D,Q},{F,X},{A,P},{B,N},{M,Y},{C,W}

DQFXAPBNMYCW

发表于 2015-11-24 18:19:53 回复(0)

码农改造地球

二路归并排序是归并排序算法中,自底向上的排序算法。

第一趟：相邻两个排序。

第二趟：2与2 排序。

第三趟：4与4排序。

。。。

若某一趟归并扫描到最后，剩下的元素个数不足两个子序列的长度时：

1.若剩下的元素个数大于一个子序列的长度 t 时，则再调用一次归并子算法 merge 将剩下的两个不等长的子序列合并成一个有序子序列

2.若剩下的元素个数小于或者等于一个子序列的长度 t 时，只须将剩下的元素依次复制到前一个子序列后面。

发表于 2015-09-02 21:58:32 回复(0)

丶花花

如果是二路归并的话，第一次是{D,Q},{F,X},{A,P},{B,N},{M,Y},{C,W}

那么第二次就是 {D, F, Q,X},{A, B ,N, P},{C,M,W,Y}

那么第三次怎么排？

我认为第一次应该是{ DQ}，{F}，{AX}，{P}，{BN}，{Y}，{CM}，{W}

每次排序应该都是偶数组才对吧

发表于 2017-03-02 22:25:43 回复(1)

追风筝的人

void Merge_Sort_Array(int *arr, int start, int mid, int last, int *temp){	
	int index = 0;
	int i = start;
	int j = mid +1;
	while(i <= mid && j <= last){
		if(arr[i] >= arr[j]){
			temp[index++] = arr[j++];
		}else{
			temp[index++] = arr[i++];
		}
	}
	while(i <= mid){
		temp[index++] = arr[i++];
	}
	while(j <= last){
		temp[index++] = arr[j++];
	}
	for(i = 0; i < index; i++){
		arr[start + i] = temp[i];
	}
}
void Merge_Sort(int *arr, int head, int tail, int *temp){
	int mid = (head + tail) /2;
	if(head < tail){
		//使数组的左边有序
		Merge_Sort(arr, head, mid, temp);
		//使数组的右边有序
		Merge_Sort(arr, mid + 1, tail, temp);
		//合并数组
		Merge_Sort_Array(arr, head, mid, tail, temp);			
	}

二路归并其实就是归并排序的思路：数组通过递归将数组分成1/2 ,然后每个子部分再分成1/2,......直到每个子部分只有一个元素的时候，递归返回，开始比较合并相邻的两个元素（例如 arr[0]、 arr[1]）、使得每个子部分都是有序的，然后再将相邻子部分合并，最终使得数组有序。

本题中问扫描一趟之后结果是什么，扫描一趟后，使得每两个相邻的元素进行了比较{Q、D}、{F、X}、{A、P}、{N、B}、{Y、M}、{C、W} ,比较后的结果是：{D、Q}、{F、X}、{A、P}、{B、N}、{M、Y}、{C、W}.所以结果是DQFXAPBNMYCW.

发表于 2016-04-16 18:01:18 回复(0)

Rico123

我也误解题义了，两路归并算法与归并排序是两码事。

发表于 2017-06-22 20:46:32 回复(0)

黄小斜

从头到尾选相邻的两个数两两归并

发表于 2017-04-03 16:35:06 回复(0)

sunlight_run

二路并归，先将数组分成n/2或者n/2+1组，然后每一组做比较

发表于 2017-06-02 09:15:08 回复(0)

philian

原来不是递归的归并排序吗= =

发表于 2016-12-18 11:44:14 回复(0)

胡辣汤

顺序如下

{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,W,Y}

二路归并第三次合并

{A,B,D,F,N,P,Q,X} {C,M,W,Y}

二路归并第四次合并

{A,B,C,D,F,M,N,P,Q,W,X,Y}

所以答案为

DQFXAPBNMYCW

发表于 2016-09-07 16:58:46 回复(0)

happylife

为什么是两两归并啊？源代码拆分的时候总是取数组中间递归调用到最后成一个元素。再归并的时候是返回去的过程会是前两个归并然后再和第三个数归并啊

发表于 2016-05-15 00:37:31 回复(0)

牛客626954号

这应该是设计思路吧如果用递归实现所谓的一趟扫描也未必有意义对于非递归形式不太清楚怎么实现

发表于 2015-09-05 12:11:34 回复(0)

龙崎努斯

额，二路归并不是从中间切成两半，然后进行类似归并排序的做法吗？

发表于 2015-09-01 16:13:59 回复(4)

aaronyoung

DQFXAPBNMYCW

发表于 2015-08-31 16:39:27 回复(0)

小V变大牛

我明明写了，怎么提交后又没了？

发表于 2015-08-24 16:02:45 回复(0)

进击的攻城狮

怎么刚刚我要提交答案就是输入不了。。。APP有bug？

发表于 2015-07-15 16:26:16 回复(1)

ABCD

DQFXAPBNMYCW

发表于 2015-06-26 08:55:31 回复(0)

设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W

问题信息

热门推荐

相关试题