歸并排序是另一類不同的排序方法，所謂歸并,就是把兩個或者兩個以上的有序表合并成一個新的有序表的過程。

歸并排序的基本思想:

將一個含有n個序列的有序表看成是n個長度為1的有序表,然后兩兩歸并,得到[n/2]個長度為2的有序表,然后再兩兩歸并,直到得到一個長度為n的有序表為止。

下面是歸并排序的一個簡單的例子:

初始值 【49】 【38】 【65】 【97】 【76】 【13】 【27】

看成由長度為1的7個子序列組成

第一次合并之后 【38 49】 【65 97】 【13 76】 【27】

看成由長度為1或2的4個子序列組成

第二次合并之后 【38 49 65 97】 【13 27 76】

看成由長度為4或3的2個子序列組成

第三次合并之后 【13 27 38 49 65 76 97】

歸并排序的JAVA實現(xiàn):

public class MergeSort {

/**

* 歸并排序 先將初始的序列表看成是n個長度為1的有序表 (1)定義指針i,指向第一個序列表的第一個元素

* (2)定義指針j，指向第二個序列表的第一個元素 (3)比較i,j指向的元素大小，若前者大，將后者插入到新表中 否則，把前者插入到后表中

* (4)直到取完第一個序列表或者第二個序列表為止

*

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] num = { 51, 38, 49, 27, 62, 05, 16 };

int[] num1 = new int[7];

num = mergesort(num, 0, num.length - 1, num1);

for (int i : num) {

System.out.print(i + " ");

}

}

private static int[] mergesort(int[] num, int s, int t, int[] num1) {

int m;

int[] num2 = new int[t + 1];

if (s == t)

num1[s] = num[s];

else {

m = (s + t) / 2;

mergesort(num, s, m, num2);//左半部分遞歸調用

mergesort(num, m + 1, t, num2);//右半部分遞歸調用

merg(num2, s, m, t, num1);// 由num2去歸并，返回的值放到num1中,num1賦新值，其實就是更新num2,然后讓num2再去歸并，返回新的num1

}

return num1;

}

//有序表的合并

private static void merg(int[] num, int l, int m, int n, int[] num1) {

System.out.print("l=" + l + " m=" + m + " n=" + n);

System.out.println();

int i, j, k;

i = l;

j = m + 1;

k = l;

while (i <= m && j <= n) {

if (num[i] < num[j])

num1[k++] = num[i++];

else {

num1[k++] = num[j++];

}

}

while (i <= m) {

num1[k++] = num[i++];

}

while (j <= n) {

num1[k++] = num[j++];

}

}

}

性能分析:

時間復雜度:

由于歸并的趟數(shù),等于樹的高度Logn,每趟歸并需要移動記錄n次,因此歸并排序的時間復雜度為nlogn.

空間復雜度:

從上面的算法可以看出,需要一個輔助空間num2,其長度等于n，所以歸并排序的輔助空間為O(n).

穩(wěn)定性:

歸并排序不涉及到交換,因此它是一種穩(wěn)定的排序算法。

歸并排序是典型的用空間去換取時間,它的時間開銷比簡單排序要優(yōu)越，但需要與序列等長的輔助空間。