001什么是歸并排序？

1)歸并排序采用了分治策略（divide-and-conquer），就是將原問題分解為一些規(guī)模較小的相似子問題，然后遞歸解決這些子問題，最后合并其結(jié)果作為原問題的解。

2)算法圖解

【1】如圖：先將數(shù)組分兩半，左邊是【2、9、5、4】，右邊是【8、1、6、7】；

【2】將左邊【2、9、5、4】繼續(xù)分兩半，左邊是【2、9】，右邊是【5、4】；

【3】將【2、9】繼續(xù)分兩半，左邊是【2】，右邊是【9】；將【5、4】繼續(xù)分兩半，左邊是【5】，右邊是【4】；

【5】創(chuàng)建臨時(shí)輔助數(shù)組，將左邊【2】和右邊【9】通過比較大小進(jìn)行合并【2、9】；

【6】創(chuàng)建臨時(shí)輔助數(shù)組，將左邊【5】和右邊【4】通過比較大小進(jìn)行合并【4、5】；

【7】創(chuàng)建臨時(shí)輔助數(shù)組，將左邊【2、9】和右邊【4、5】通過比較大小進(jìn)行合并【2、4、5、9】，同樣的道理得到【1、8、6、7】；

【8】創(chuàng)建臨時(shí)輔助數(shù)組，將左邊【2、4、5、9】和右邊【1、8、6、7】通過比較大小進(jìn)行合并【1、2、4、5、6、7、8、9】；

002歸并排序的代碼實(shí)現(xiàn)？

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關(guān)于歸并排序敘述正確的是( ).

A. 歸并排序使用了分治策略的思想
B. 歸并排序使用了貪心策略的思想
C. 子序列的長(zhǎng)度一定相等
D. 歸并排序是穩(wěn)定的
答案：AD
解析：暫無(wú)解析

004若外部存儲(chǔ)上有3110400個(gè)記錄，做6路平衡歸并排序，計(jì)算機(jī)內(nèi)存工作區(qū)能容納400個(gè)記錄，則排序好所有記錄，需要作幾趟歸并排序( )

A. 6
B. 3
C. 5
D. 4
答案：C
解析：每次將工作區(qū)裝滿，共計(jì)3110400/400=7776個(gè)歸并段，對(duì)于n路歸并排序，m個(gè)歸并段，需要?dú)w并排序的次數(shù)為次，代入數(shù)據(jù)得到答案為5，所以C正確。