数据结构与算法(22): 排序- 归并排序

发表于   |   分类于

  归并排序的基本思想：将两个有序数列合并成一个有序数列，具体实现包括“从上往下”和“从下往上”2种方式。
  时间复杂度：O($N\log{N}$)。
  空间复杂度：O($N$)。（临时数组）
  归并排序是稳定的。

  1. 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；重复下去直到合并成一个数列为止。
  2. 从下往上的归并排序：
    • 分解：将当前区间一分为二，即求分裂点 mid = (low + high)/2;
    • 求解：递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1。
    • 合并：将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
    /**
     * 归并排序：从大到小
     */
    public class MergeSort extends Sort {
    private static int[] tmpArray = new int[100];
    /**
     * 自上而下：利用递归实现的分治思想
     *
     * @param a
     */
    public static void sortTopDown(int[] a, int low, int high) {
        if (high <= low) return;
        int mid = low + (high - low) / 2;
        sortTopDown(a, low, mid);
        sortTopDown(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    /**
     * 自下而上
     * 先归并那些微型数组, 然后再成对归并得到的子数组。
     * 1、首先进行两两归并(把每个元素想象成一个大小为1的数组)
     * 2、然后四四归并(将两个大小为2的数组归并成一个有4个元素的数组)
     * 3、然后是八八归并....一直下去
     *
     * @param a
     */
    public static void sortDownTop(int[] a) {
        for (int sz = 1; sz < a.length; sz *= 2) {
            System.out.println("-------每组" + sz + "个元素------");
            for (int i = 0; i < a.length - sz; i += sz * 2) {
                merge(a, i, i + sz - 1, Math.min(i + sz * 2 - 1, a.length - 1));
            }
        }
    }
    private static void merge(int[] a, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            tmpArray[i] = a[i];
        }
        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            if (i > mid) a[k] = tmpArray[j++];
            else if (j > high) a[k] = tmpArray[i++];
            else if (tmpArray[i] < tmpArray[j]) a[k] = tmpArray[j++];
            else a[k] = tmpArray[i++];
        }
        print(a);
    }
}

感谢:http://www.cnblogs.com/skywang12345/p/3602369.html