一、概述
????歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個(gè)典型應(yīng)用。
????將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段之間有序。將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
二、歸并排序的基本思想
????將待排序序列R[0...n-1]看成是n個(gè)長(zhǎng)度為1的有序序列，將相鄰的有序表成對(duì)歸并，得到n/2個(gè)長(zhǎng)度為2的有序表；將這些有序序列再次歸并，得到n/4個(gè)長(zhǎng)度為4的有序序列；如此反復(fù)，最后得到一個(gè)長(zhǎng)度為n的有序序列。
歸并排序需要做兩件事：
1）分解：將序列每次折半劃分
2）合并：將劃分后的序列段兩兩合并后排序
如何合并？
????在每次合并過(guò)程中，都是對(duì)兩個(gè)有序的序列段進(jìn)行合并，然后再排序。這兩個(gè)有序的序列段分別為R[low, mid]和R[mid+1, high]，先將它們合并到一個(gè)局部的暫存數(shù)組R2中，待合并完成后再將R2復(fù)制回R中。
????每次從兩個(gè)段中取出一個(gè)記錄進(jìn)行關(guān)鍵字的比較，將較小者放入R2中，最后將各段中余下的部分直接復(fù)制到R2中。經(jīng)過(guò)這樣的過(guò)程，R2已經(jīng)是一個(gè)有序的序列，再將其復(fù)制回R中，一次合并排序就完成了。
在某趟歸并中，設(shè)各子表的長(zhǎng)度為gap，則歸并前R[0...n-1]中共有n/gap個(gè)有序的子表：R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。
在將相鄰的子表歸并時(shí)，需要對(duì)表的特殊情況進(jìn)行處理：
1）若子表個(gè)數(shù)為奇數(shù)，最后一個(gè)子表無(wú)須和其他子表歸并（即本趟處理輪空）；
2）若子表個(gè)數(shù)為偶數(shù)，到最后一對(duì)子表中后一個(gè)子表區(qū)間的上限為n-1；
三、排序性能
時(shí)間復(fù)雜度：歸并排序的形式就是一棵二叉樹(shù)，需要遍歷的次數(shù)就是二叉樹(shù)的深度，時(shí)間復(fù)雜度是O(nlogn)。
空間復(fù)雜度：算法處理過(guò)程中，需要一個(gè)大小為n的臨時(shí)存儲(chǔ)空間用來(lái)保存合并序列。
算法穩(wěn)定性：在歸并排序中，相等元素的順序不會(huì)改變，所以它是穩(wěn)定的算法。
總結(jié)：
1）時(shí)間復(fù)雜度：O(nlogn)
2）空間復(fù)雜度：O(n)
3）穩(wěn)定性：穩(wěn)定
4）復(fù)雜性：較復(fù)雜
四、選擇對(duì)比
1）空間復(fù)雜度考慮：選擇優(yōu)先級(jí)為[堆排序>快速排序>歸并排序]。
2）穩(wěn)定性考慮：應(yīng)選歸并排序，堆排序和快速排序都是不穩(wěn)定的。
3）平均排序速度考慮：應(yīng)選快速排序。
五、代碼實(shí)現(xiàn)
import java.util.Arrays;
/**
* 歸并排序
* 效率O（nlogn），歸并的最佳、平均和最糟用例效率之間沒(méi)有差異，適用于排序大列表，基于分治法。
*/
public class MergeSort {
????public static void main(String[] args) {
????????int[] array = {9, 1, 5, 3, 4, 2, 6, 8, 7};
????????MergeSort merge = new MergeSort();
????????System.out.println("排序前:"+Arrays.toString(array));
????????merge.sort(array);
????????System.out.println("排序后:"+Arrays.toString(array));
????}
????private static int[] sort(int[] list){
????????for(int gap = 1;gap <list.length; gap = 2*gap){
????????????MergePass(list,gap,list.length);
????????????System.out.println("gap="+gap+":"+Arrays.toString(list));
????????}
????????return list;
????}
????private static void MergePass(int[] arr,int gap,int length){
????????int i=0;
????????// 歸并gap長(zhǎng)度的兩個(gè)相鄰子表
????????for(i=0;i+2*gap-1 < length;i = i+2*gap){
????????????Merge(arr, i, i + gap - 1, i + 2 * gap - 1);
????????}
????????// 余下兩個(gè)子表，后者長(zhǎng)度小于gap
????????if (i + gap - 1 < length) {
????????????Merge(arr, i, i + gap - 1, length - 1);
????????}
????}
????private static void Merge(int[] arr,int low,int mid,int high){
????????int i=low;// i是第一段序列的下標(biāo)
????????int j = mid +1;// j是第二段序列的下標(biāo)
????????int k = 0;// k是臨時(shí)存放合并序列的下標(biāo)
????????int[] array2 = new int[high - low + 1]; // array2是臨時(shí)合并序列
????????// 掃描第一段和第二段序列，直到有一個(gè)掃描結(jié)束
????????while (i <= mid && j <= high) {
????????????// 判斷第一段和第二段取出的數(shù)哪個(gè)更小，將其存入合并序列，并繼續(xù)向下掃描
????????????if (arr[i] <= arr[j]) {
????????????????array2[k] = arr[i];
????????????????i++;
????????????????k++;
????????????} else {
????????????????array2[k] = arr[j];
????????????????j++;
????????????????k++;
????????????}
????????}
????????// 若第一段序列還沒(méi)掃描完，將其全部復(fù)制到合并序列
????????while(i <= mid){
????????????array2[k] = arr[i];
????????????i++;
????????????k++;
????????}
????????// 若第二段序列還沒(méi)掃描完，將其全部復(fù)制到合并序列
????????while(j <= high){
????????????array2[k] = arr[j];
????????????j++;
????????????k++;
????????}
????????// 將合并序列復(fù)制到原始序列中
????????for (k = 0, i = low; i <= high; i++, k++) {
????????????arr[i] = array2[k];
????????}
????}
}
運(yùn)行結(jié)果:
排序前: ? ? 9???1???5???3???4???2???6???8???7??
gap?=?1:???1???9???3???5???2???4???6???8???7??
gap?=?2:???1???3???5???9???2???4???6???8???7??
gap?=?4:???1???2???3???4???5???6???8???9???7??
gap?=?8:???1???2???3???4???5???6???7???8???9??
排序后: ? ? 1???2???3???4???5???6???7???8???9 ?
