数据结构和算法

归并排序

分治法

将问题分解为若干个规模小但类型原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来求原问题的解.
三个步骤
分解:把问题分解成若干个规模小的子问题,这些子问题是原问题的规模小的实例
解决:递归求解各个子问题,如果规模足够小,直接求解
合并:根据子问题的解,求原问题解

排序原理

分解:把待排序N个元素的序列分解成两个N/2个元素的子序列
解决:递归地排序两个子序列,但子序列长度为1.递归返回
合并:把两个已排序的子序列,合并成一个已排序的序列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
   public static void mergeSort(int[] A, int p, int r){
if (p < r) {
    int q = (p + r)/2;
    mergeSort(A, p, q);
    mergeSort(A, q+1, r);
    merge(A, p, q, r);
}
   }
   public static void merge(int[] A, int p, int q, int r){
       int[] lp = new int[q - p + 1];
       int[] lq = new int[r - q];
       System.arraycopy(A, p, lp, 0, q - p + 1);
       System.arraycopy(A, q+1, lq, 0, r - q);
       int k = p, i, j;
       for (i = 0, j = 0; i < lp.length && j < lq.length; k++) {
           if (lp[i] > lq[j]) {
               A[k] = lq[j];
               j++;
           } else {
               A[k] = lp[i];
               i++;
           }
       }
       if (i < lp.length) {
           for (;i<lp.length;i++,k++) {
               A[k] = lp[i];
           }
       }
       if (j < lq.length) {
           for (;j<lq.length;j++,k++) {
               A[k] = lq[j];
           }
       }
   }

性能分析

merge方法合并N/2长两个序列需要N长时间.当子序列长度为1,递归返回时,merge合并N/2对长度为1的子序列,即总时间N.
然而这递归过程可以建立一个二叉树,N个元素当做叶子节点.非叶子节点即是两个子节点序列合并而成. 所以这颗树的高度是logN,每一层合并的时间是N.因此归并排序时间复杂度是:NlogN