归并排序(英语:Merge sort),是创建在归并操作上的一种有效的排序算法,效率为\(O(N\,log\,N)\)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

归并排序的中心思想

归并排序的核心就是“并”,其思想也很简单,只要把一个序列一分为二,并且不断分下去,经过将最后分出来的小序列排序后,在将它们逐渐合并起来,直到合并成一个序列为止,算法结束。
下面是采自Wikipedia上归并排序词条的一个动图,很形象的解释了归并排序的过程:
merge-sort-on-wikipedia

归并排序的时间复杂度与稳定性

首先我们要知道算法稳定性的定义是什么,举个栗子:
假设在序列中存在\(a[i] = a[j]\),若在进行排序之前,\(a[i]\)在\(a[j]\)之前,且在排序之后,\(a[i]\)仍然处于\(a[j]\)之前,那么我们可以说这个算法是稳定的。
关于时间复杂度,我们假设即将被排序的序列中有数\(N\)个,遍历其一趟的复杂度为\(O(N)\),那么我们需要遍历多少次?归并排序的形式看下图是一颗二叉树,我们需要遍历的次数是这颗二叉树的深度,那么我们可以得出时间复杂度为\(O(N\,log\,N)\)

自上而下的归并排序(Top-down)

我们这样想,如果归并排序能将一个大的序列的两个子序列进行排序,那么它就能通过归并排序两个子序列来将整个序列排序。在进行归并排序的时候,我们需要一个辅助空序列,我们需要将此次归并排序涉及到的所有元素复制到辅助序列中,然后再将归并的结果放回到原序列中。

merge-sort-top-down

自上而下的归并排序分为三个步骤:

  1. 分解(一分为二的操作):将当前区间的序列根据\((lo + hi) \div 2\),求出其分裂点,也就是\(mid\)。
  2. 归:通过递归的形式来对\([lo\dots mid]\)和\([mid+1\dots hi]\)进行归并排序,递归条件是当子序列为\(1\)时。
  3. 并:将已经排序好的两个有序子区间\([lo\dots mid]\)和\([mid+1\dots hi]\)进行合并成\([lo\dots hi]\)一个有序的序列。

代码实现

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
package net.sunzhenyu.miscellaneous.dsa.sort;

public class MergeSort implements Sort {

@Override
public void sort(Comparable[] c) {
Comparable[] aux = new Comparable[c.length];
sort(c, aux, 0, c.length - 1);
}

private void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) {
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}

private void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// Copy
for (int i = lo; i <= hi; i++) {
aux[i] = a[i];
}

// Merge
int l = lo;
int r = mid + 1;
for (int i = lo; i <= hi; i++) {
if (l > mid) {
// 当左半边用尽,取右边元素
a[i] = aux[r++];
} else if (r > hi) {
// 当右半边用尽,取左边元素
a[i] = aux[l++];
} else if (less(aux[r], aux[l])) {
// 右半边的当前元素小于左半边的当前元素(取右半边)
a[i] = aux[r++];
} else {
// 左半边的当前元素小于右半边的当前元素(取左半边)
a[i] = aux[l++];
}
}
}

}

自下而上的归并排序(Bottom-up)

自下而上的归并排序与自上而下的归并排序思想正好相反,我们首先要将\(length = N, N > 1\)的序列抽象成共\(N\)个子序列,然后将其两两合并为若干个长度为\(2\)的子序列,然后再将其两两合并,直到合并成为一个序列为止,算法结束,我们会得到一个我们想要的经过归并排序的有序序列。

1
2
3
4
5
6
7
8
9
10
11
public void bottomUpSort(Comparable[] c) {
int length = c.length;
Comparable[] aux = new Comparable[length];
for (int i = 1; i < length; i *= 2) {
for (int lo = 0; lo < length - i; lo += i + i) {
int mid = lo + i - 1;
int hi = Math.min(lo + i + i - 1, length - 1);
merge(c, aux, lo, mid, hi);
}
}
}

归并排序的优化

对于目前所写的归并排序还有可以优化的空间,我们将从以下三点来大幅度提高我们归并排序算法的运行速度:

  1. 如果将要排序的序列小于指定的长度,我们可以选用插入排序(Insertion Sort)算法将其完成,因为递归会使得小规模问题中方法的调用过于频繁,只要我们将它们的处理方法进行改进就能改进整个算法。插入排序算法(Insertion Sort)或者选择排序算法(Selection Sort)非常的简单,有可能它们会在对于小规模问题的处理上优于归并排序算法。
  2. 我们在进行归并排序的时候,可以增加一个对于当前子序列是否已经有序的判断,通过对\(a[mid]\)是否小于\([mid + 1]\)的判断,我们就可以选择跳过merge()方法。这个改动并不会影响到归并排序的递归调用,通过这个改进我们可以让任意有序子序列算法的运行时间变为线性。
  3. 为了节省元素复制到辅助序列作用的时间,可在递归的每个层次交换原序列与辅助序列的角色(此优化只是在时间上优化,无法影响到空间)。
    下面我们来看下最终优化过的归并排序的代码:
    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
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    package net.sunzhenyu.miscellaneous.dsa.sort;

    public class MergeSort implements Sort {

    @SuppressWarnings("all")
    private final int SORT_CAPACITY = 15;

    @Override
    public void sort(Comparable[] c) {
    Comparable[] aux = new Comparable[c.length];
    sort(c, aux, 0, c.length - 1);
    }

    public void bottomUpSort(Comparable[] c) {
    int length = c.length;
    Comparable[] aux = new Comparable[length];
    for (int i = 1; i < length; i *= 2) {
    for (int lo = 0; lo < length - i; lo += i + i) {
    int mid = lo + i - 1;
    int hi = Math.min(lo + i + i - 1, length - 1);
    merge(c, aux, lo, mid, hi);
    }
    }
    }

    private void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo + SORT_CAPACITY) {
    insertionSort(aux, lo, hi);
    return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(aux, a, lo, mid);
    sort(aux, a, mid + 1, hi);
    if (!less(a[mid + 1], a[mid])) {
    System.arraycopy(a, lo, aux, lo, hi - lo + 1);
    return;
    }
    merge(a, aux, lo, mid, hi);
    }

    private void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // Copy
    for (int i = lo; i <= hi; i++) {
    aux[i] = a[i];
    }

    // Merge
    int l = lo;
    int r = mid + 1;
    for (int i = lo; i <= hi; i++) {
    if (l > mid) {
    a[i] = aux[r++];
    } else if (r > hi) {
    a[i] = aux[l++];
    } else if (less(aux[r], aux[l])) {
    a[i] = aux[r++];
    } else {
    a[i] = aux[l++];
    }
    }
    }

    private void insertionSort(Comparable[] c, int lo, int hi) {
    for (int i = lo; i <= hi; i++) {
    for (int j = i; j > lo && less(c[j], c[j - 1]); j--) {
    exchange(c, j, j - 1);
    }
    }
    }

    private void exchange(Comparable[] c, int i, int j) {
    Comparable oldValue = c[i];
    c[i] = c[j];
    c[j] = oldValue;
    }

    }