归并排序面试题

001什么是归并排序？

1)归并排序采用了分治策略（divide-and-conquer），就是将原问题分解为一些规模较小的相似子问题，然后递归解决这些子问题，最后合并其结果作为原问题的解。

2)算法图解

【1】如图：先将数组分两半，左边是【2、9、5、4】，右边是【8、1、6、7】；

【2】将左边【2、9、5、4】继续分两半，左边是【2、9】，右边是【5、4】；

【3】将【2、9】继续分两半，左边是【2】，右边是【9】；将【5、4】继续分两半，左边是【5】，右边是【4】；

【5】创建临时辅助数组，将左边【2】和右边【9】通过比较大小进行合并【2、9】；

【6】创建临时辅助数组，将左边【5】和右边【4】通过比较大小进行合并【4、5】；

【7】创建临时辅助数组，将左边【2、9】和右边【4、5】通过比较大小进行合并【2、4、5、9】，同样的道理得到【1、8、6、7】；

【8】创建临时辅助数组，将左边【2、4、5、9】和右边【1、8、6、7】通过比较大小进行合并【1、2、4、5、6、7、8、9】；

002归并排序的代码实现？

public static void mergeSort(int[] arr) { 
    if (arr == null || arr.length < 2) {
	    return;
    }
    process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {
    if (L == R) {
	    return;
	}
	int mid = L + ((R - L) >> 1);
	process(arr, L, mid);
	process(arr, mid + 1, R);
	merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R) {		
    int[] help = new int[R - L + 1];
	int i = 0;
	int p1 = L;
	int p2 = M + 1;
	while (p1 <= M && p2 <= R) {
		help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= M) {
		help[i++] = arr[p1++];
	}
	while (p2 <= R) {
		help[i++] = arr[p2++];
	}
	for (i = 0; i < help.length; i++) {
		arr[L + i] = help[i];
	}
}

003关于归并排序叙述正确的是( ).

A. 归并排序使用了分治策略的思想
B. 归并排序使用了贪心策略的思想
C. 子序列的长度一定相等
D. 归并排序是稳定的
答案：AD
解析：暂无解析

004若外部存储上有3110400个记录，做6路平衡归并排序，计算机内存工作区能容纳400个记录，则排序好所有记录，需要作几趟归并排序( )

A. 6
B. 3
C. 5
D. 4
答案：C
解析：每次将工作区装满，共计3110400/400=7776个归并段，对于n路归并排序，m个归并段，需要归并排序的次数为次，代入数据得到答案为5，所以C正确。