排序算法之归并排序(Java)

若人们不相信数学简单,只因他们未意识到生命之复杂。
—— 约翰·冯·诺伊曼

归并排序简介

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

归并操作

归并操作(merge),也叫归并算法,是指将两个已经排序的序列合并成一个序列的操作。
归并操作有两种方法可实现:迭代法递归法。本篇主要介绍性能最优的迭代法。

归并排序思想

假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到$\lceil n/2 \rceil$($\lceil x \rceil$表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,···,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为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
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
/**
* @description 对顺序表作归并非递归排序
* @author GongchuangSu
* @since 2016.03.27
* @version v1.0
*/

public class MergeSort {
public static void main(String[] args) {
// SR[0]和TR[0]用作哨兵或临时变量
int[] SR = {
1000, 50, 10, 90, 30, 70, 40, 80, 60, 20
};
int[] TR = new int[10];
TR[0] = 1000;
int k = 1;
while (k < SR.length) {
MergePass(SR, TR, k, SR.length - 1);
k = 2 * k;
MergePass(TR, SR, k, SR.length - 1);
k = 2 * k;
}
for (int i = 0; i < TR.length; i++) {
System.out.println( String.valueOf(SR[i]));
}
}

/**
* 功能:将SR[]中相邻长度为s的子序列两两归并到TR[]
*/

private static void MergePass(int SR[], int TR[], int s, int n) {
int i = 1;
int j;
while (i <= n - 2 * s + 1) {
Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
i = i + 2 * s;
}
if (i < n - s + 1) // 归并最后两个序列
Merge(SR, TR, i, i + s - 1, n);
else // 若最后只剩下单个子序列
for (j = i; j <= n; j++)
TR[j] = SR[j];
}

/**
* 功能:将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n]
*/

private static void Merge(int SR[], int TR[], int i, int m, int n) {
int j, k, l;
// 将SR中记录由小到大归并入TR
for (j = m + 1, k = i; i <= m && j <= n; k++) {
if (SR[i] < SR[j]) {
TR[k] = SR[i];
i = i + 1;
} else {
TR[k] = SR[j];
j = j + 1;
}
}
// 将剩余的SR[i...m]复制到TR
if (i <= m) {
for (l = 0; l <= m - i; l++)
TR[k + l] = SR[i + l];
}
// 将剩余的SR[j..n]复制到TR
if (j <= n) {
for (l = 0; l <= n - j; l++)
TR[k + l] = SR[j + l];
}
}
}

输出结果:

1
2
3
4
5
6
7
8
9
10
1000
10
20
30
40
50
60
70
80
90

算法分析

时间复杂度

对于递归法,总的时间复杂度为$\Theta(n\log n)$,而且是其最好、最坏、平均的时间性能。
对于迭代法,其最优时间复杂度为$\Theta(n)$。

空间复杂度

对于递归法,其空间复杂度为$\Theta(n + \log n)$。
对于迭代法,其空间复杂度为$\Theta(n)$。

稳定性

归并排序是一种稳定的排序方法。