歸并排序中的“歸并”的意思是將兩個(gè)或者兩個(gè)以上的有序表組合成一個(gè)新的有序表,。他的實(shí)現(xiàn)無(wú)論是順序存儲(chǔ)結(jié)構(gòu)還是鏈表結(jié)構(gòu),，都可以在O(m n)的時(shí)間級(jí)上實(shí)現(xiàn),。

復(fù)雜度：

時(shí)間復(fù)雜度：O(nlogn)

空間復(fù)雜度：O(n)

用途：

1、排序（速度僅次于快速排序,，但較穩(wěn)定）

2,、求逆序?qū)?shù)

在實(shí)現(xiàn)單數(shù)組的歸并排序之前，首先了解一下雙數(shù)組的歸并排序

這個(gè)雙數(shù)組歸并的前提是兩個(gè)數(shù)組a和b都是已經(jīng)排序好的

Java代碼  

1. package sort;   
2.   
3. import java.util.Arrays;   
4.   
5. public class Test1 {   
6.     public static void main(String args[])   
7.     {   
8.         int a[]={1,2,3,4,6,7,8,10};   
9.         int b[]={1,2,5,9};   
10.         int c[] = new int[a.length b.length];   
11.         mergeSort(a,a.length,b,b.length,c);   
12.         System.out.println(Arrays.toString(c));   
13.     }   
14.     public static void mergeSort(int a[],int n,int b[],int m,int c[])   
15.     {   
16.         int i,j,k;   
17.         i=j=k=0;   
18.         //只有滿足i<n&&j<m才執(zhí)行,，分別掃描兩個(gè)數(shù)組,，將數(shù)組中的元素進(jìn)行對(duì)比,，從小到大賦值給臨時(shí)數(shù)組c   
19.         while(i<n&&j<m)   
20.         {   
21.             if(a[i]<b[j])   
22.                 c[k ]=a[i ];   
23.             else  
24.                 c[k ]=b[j ];   
25.         }   
26.         //將剩余的a數(shù)組的元素放入c中   
27.         while(i<n)   
28.         {   
29.             c[k ]=a[i ];   
30.         }   
31.         //將剩余的b數(shù)組的元素放入c中   
32.         while(j<m)   
33.         {   
34.             c[k ]=b[j ];   
35.         }   
36.     }   
37. }  

運(yùn)行結(jié)果如下：

[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]

下面開(kāi)始實(shí)現(xiàn)單數(shù)組的歸并排序算法

例如：49  38  65  97  76  13  27

思想：首先將數(shù)組中個(gè)單獨(dú)的一個(gè)元素作為一個(gè)已經(jīng)排序好的序列，然后,，將兩兩相鄰的元素進(jìn)行歸并排序,，依次類推，直到最后歸并為一個(gè)排序好的序列

 如上圖：

首先將每個(gè)元素作為一個(gè)已經(jīng)排序好的序列,，一共7個(gè)序列

然后,，將每?jī)蓚€(gè)相鄰的序列歸并為一個(gè)序列，如49 38歸并排序后變成 38 49,，依次分成了4個(gè)序列,，然后再將之前已經(jīng)排序好的兩個(gè)相鄰的序列進(jìn)行排序，變成2個(gè)序列,，每個(gè)序列都是排序好的,，最后歸并為一個(gè)排序好的序列

實(shí)現(xiàn)代碼：

Java代碼  

1. package sort;   
2.   
3. import java.util.Arrays;   
4.   
5. public class MergeSort {   
6.     public static void main(String args[])   
7.     {   
8.         int[] array = {49,38,65,97,76,13,27};   
9.         System.out.println(Arrays.toString(array));   
10.         System.out.println("---------排序前-------------");   
11.         mergeSort(array,0,array.length-1);   
12.         System.out.println("---------排序后-------------");   
13.         System.out.println(Arrays.toString(array));   
14.     }   
15.     /**  
16.      * 這里依然需要遞歸來(lái)達(dá)到數(shù)組元素的排序，如果有兩個(gè)已有元素的數(shù)組的話,，就不用這么麻煩您了  
17.      * 不過(guò)這種歸并排序依然是效率最好的排序方法之一,，而且還是穩(wěn)定的（相比快速排序，快速排序不穩(wěn)定）  
18.      */  
19.     public static void mergeSort(int array[],int low,int high)   
20.     {   
21.         if(low<high)   
22.         {      
23.             mergeSort(array,low,(low high)/2);//左邊排序   
24.             mergeSort(array,(low high)/2 1,high);//右邊排序   
25.             merge(array,low,(high low)/2,high);//將兩個(gè)序列歸并為一個(gè)序列   
26.             System.out.println(Arrays.toString(array));    
27.         }   
28.     }   
29.        
30.     public static void merge(int array[],int low,int mid,int high)   
31.     {   
32.         int temp[]=new int[high-low 1];   
33.         int i = low;   
34.         int j = mid 1;   
35.         int k=0;   
36.         /**  
37.          * 將array數(shù)組分成兩個(gè)數(shù)組來(lái)掃描,，每一次都會(huì)將前后相鄰的兩個(gè)有序的序列歸并為一個(gè)有序的序列  
38.          */  
39.         while(i<=mid&&j<=high)   
40.         {   
41.             if(array[i]<=array[j])   
42.                 temp[k ]=array[i ];   
43.             else  
44.                 temp[k ]=array[j ];      
45.         }   
46.         //下面這兩種while循環(huán)每次只執(zhí)行其中一個(gè)   
47.         //將剩余的array[i]存入temp中   
48.         while(i<=mid)   
49.         {   
50.             temp[k ]=array[i ];   
51.         }   
52.         //將剩余的array[j]存放到temp中   
53.         while(j<=high)   
54.         {   
55.             temp[k ]=array[j ];   
56.         }   
57.         for(int m=0;m<temp.length;m )   
58.         {   
59.             array[low m]=temp[m];   
60.         }   
61.            
62.     }   
63. }  

運(yùn)行結(jié)果如下：

[49, 38, 65, 97, 76, 13, 27]

---------排序前-------------

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 76, 13, 27]

[38, 49, 65, 97, 13, 76, 27]

[38, 49, 65, 97, 13, 27, 76]

[13, 27, 38, 49, 65, 76, 97]

---------排序后-------------

[13, 27, 38, 49, 65, 76, 97]