归并排序

发表于:，更新于:，By Guodong
大纲
  1. 1. 算法介绍
  2. 2. 代码实现

本文介绍归并排序的原理和实现。

算法介绍

相对于快速排序，归并排序的思想比较简单。
如果你认为快速排序比较简单的话，建议你看一下我写的快速排序算法，如果不认同我的看法可以给我留言。

这个太简单了，就简单介绍下：
1分2，2分4，4分8，直到每个数组长度不大于2。

对每个数组分别排序，排序后，由同一个数组分成的已排序的两个子数组逐层向上进行合并。

代码实现

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
public static void mergeSort(int[] a) {
    mergeSort(a, 0, a.length - 1);
}

private static void mergeSort(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int center = (left + right) / 2;
    mergeSort(a, left, center);
    mergeSort(a, center + 1, right);
    merge(a, left, center, right);
}

private static void merge(int[] a, int left, int center, int right) {
    int[] tmp = new int[right - left + 1];

    int i = left;
    int j = center + 1;
    int k = 0;

    while (i <= center && j <= right)
        tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];

    while (i <= center)
        tmp[k++] = a[i++];

    while (j <= right)
        tmp[k++] = a[j++];

    System.arraycopy(tmp, 0, a, left, tmp.length);
}