屬性

????????歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使 子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。 歸并排序核心步驟：

????????歸并排序總結(jié)

????????1. 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。

????????2. 時(shí)間復(fù)雜度：O(N*logN)

????????3. 空間復(fù)雜度：O(N)

????????4. 穩(wěn)定性：穩(wěn)定

代碼及注釋（遞歸實(shí)現(xiàn)）

    //mergeSort是歸并排序提供使用的方法public static void mergeSort(int[]arr){//用mergeSortChild進(jìn)行遞歸排序mergeSortChild(arr,0,arr.length-1);}private static void mergeSortChild(int[]arr,int left,int right){//出遞歸if(left>=right){return;}//先計(jì)算出要排序數(shù)據(jù)的中間位置int mid=(left+right)/2;//先分別歸并排序左邊和右邊的數(shù)據(jù)，排序好以后再將左邊和右邊的數(shù)據(jù)合并mergeSortChild(arr,left,mid);mergeSortChild(arr,mid+1,right);merge(arr,left,right);}private static void merge(int[]arr,int left,int right){int mid=(left+right)/2;//left和right范圍的數(shù)據(jù)分為了兩個(gè)部分//用s1，e1表示第一部分的數(shù)據(jù)范圍，s2，e2表示第二部分的數(shù)據(jù)范圍//兩個(gè)部分的數(shù)據(jù)分別是排序好了的，要將兩個(gè)部分的數(shù)據(jù)進(jìn)行合并int s1=left;int e1=mid;int s2=mid+1;int e2=right;//定義輔助數(shù)組help來幫助合并int[]help=new int[right-left+1];//放數(shù)據(jù)的時(shí)候有以下的幾種情況//1.兩個(gè)部分的數(shù)據(jù)還沒有哪個(gè)部分全放到help數(shù)組中int k=0;    //k是用于指向help數(shù)組的下標(biāo)while (s1<=e1&&s2<=e2){//當(dāng)s1下標(biāo)的數(shù)據(jù)比s2下標(biāo)的小時(shí)，s1下標(biāo)的數(shù)據(jù)就先放到help數(shù)組中if(arr[s1]<arr[s2]){help[k++]=arr[s1++];}else {help[k++]=arr[s2++];}}//2.s1>e1 第一部分的數(shù)據(jù)都放到了help數(shù)組中//直接將第二部分的數(shù)據(jù)全放到help數(shù)組中while (s2<=e2){help[k++]=arr[s2++];}//3.s2>e1 第二部分的數(shù)據(jù)都放到了help數(shù)組中//直接將第一部分的數(shù)據(jù)全放到help數(shù)組中while (s1<=e1){help[k++]=arr[s1++];}//此時(shí)兩個(gè)部分的數(shù)據(jù)都放到了help數(shù)組中//將數(shù)組中對應(yīng)部分的數(shù)據(jù)改為help數(shù)組中的數(shù)據(jù)（help數(shù)組中的數(shù)據(jù)是合并好了的）for(int i=left,j=0;i<=right;i++,j++){arr[i]=help[j];}}

代碼及注釋（非遞歸實(shí)現(xiàn)）
?

 //歸并排序---非遞歸public static void mergeSortNo(int[] array){//一個(gè)數(shù)據(jù)為一組int gap=1;while (gap<array.length){for(int i=0;i<array.length;i+=2*gap){int left=i;int mid=left+gap-1;int right=mid+gap;merge(array,left,mid,right);}gap=gap*2;}} //合并private static void merge(int[] array,int left,int mid,int right){int s1=left;int e1=mid;int s2=mid+1;int e2=right;//定義輔助數(shù)組int[]help=new int[right-left+1];int k=0;//兩組數(shù)據(jù)都沒放完while (s1<=e1&&s2<=e2){if(array[s1]<array[s2]){help[k++]=array[s1++];}else {help[k++]=array[s2++];}}//當(dāng)有一組中的數(shù)據(jù)放完while (s1<=e1){help[k++]=array[s1++];}while (s2<=e2){help[k++]=array[s2++];}//將合并好的數(shù)據(jù)返回給數(shù)組arrayfor (int i=0;i<help.length;i++){array[left+i]=help[i];}}