1. 归并排序算法思想
归并排序使用的是分治的思想，把问题拆分成子问题，逐个解决子问题，在把子问题的解合并，得到原问题的解。
2. 递归的归并排序
2.1. 算法描述
对于一个数组array，数组的长度是size：
- 如果size==1，那么数组已经有序了，返回；否则进行下面的步骤，
- 把原数组拆分成长度近似相等的两个子数组（如果size是奇数，那么无法平均分配），递归调用归并排序的方法，对这两个子数组进行排序；
- 把排好序的两个子数组和并在一起。
2.2. 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class MergeSortRecursively {
public static void sort(int[] array) {
sort(array,0,array.length - 1,new int[array.length]);
}
private static void sort(int[] array, int l, int r,int[] help) {
if(l == r) return;
int m = (l + r) >>> 1;
sort(array,l,m,help);
sort(array,m + 1,r,help);
merge(array,l,m,r,help);
}
private static void merge(int[] array, int l, int m ,int r, int[] help) {
int i = l, j = m + 1, k = 0;
while(i <= m && j <= r) help[k++] = array[i] <= array[j] ? array[i++] : array[j++];
while(i <= m) help[k++] = array[i++];
while(j <= r) help[k++] = array[j++];
System.arraycopy(help,0,array,l,k);
}
}
|
时间复杂度$O(N\log_2N)$，空间复杂度$O(N)$的合并辅助空间以及$O(\log_2N)$的递归栈空间。
3. 迭代的归并排序
递归版本的是从上往下的方法，大数组不断拆分成小数组。迭代的方法是从下往上的方法，先考虑合并最小的分组，然后逐渐增加分组的长度，直到整个数组变成一个分组的时候，数组就排好序了。
3.1. 算法描述
数组待排序部分的长度记为len，分组长度groupLen初始化为1；数组待排序部分开始下标l，末尾下标r；
只要groupLen<len，就执行下面的步骤：
- 使用一个变量x表示当前分组的开始位置，x初始化为l；只要x<r，执行下面的步骤；
- 如果数组剩余部分刚好够左分组的长度，或者不够左分组的长度，那么此时是没有右分组的，因此直接退出内循环；
- 否则，有右分组，那么确定右分组的结束位置y，以及左分组的结束位置mid；
- 执行merge操作
- 开始位置x = y+1；
- 如果分组长度groupLen已经超过了数组的长度了，那么退出外循环，排序结束，
- 否则groupLen *= 2
3.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
| public class MergeSortIteratively {
public static void sort(int[] array) {
sort(array,0,array.length - 1,new int[array.length]);
}
private static void sort(int[] array, int l, int r, int[] help) {
if(l == r) return;
int len = r - l + 1, groupLen = 1, x, m, y;
while(groupLen < len) {
x = l;
while(x < r) {
if((m = x + groupLen - 1) >= r) break;
y = Math.min(m + groupLen, r);
merge(array,x,m,y,help);
x = y + 1;
}
if(groupLen > (len >> 1)) break;
groupLen <<= 1;
}
}
private static void merge(int[] array, int l, int m, int r, int[] help) {
int i = l, j = m + 1, k = 0;
while(i <= m && j <= r) help[k++] = array[i] <= array[j] ? array[i++] : array[j++];
while(i <= m) help[k++] = array[i++];
while(j <= r) help[k++] = array[j++];
System.arraycopy(help,0,array,l,k);
}
}
|
时间复杂度$O(N\log_2N)$，空间复杂度$O(N)$。没有过多的系统堆栈空间。
4. 测试程序
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
| import java.util.*;
public class MergeSortTest {
public static void main(String[] args) {
int testTimes = 100_0000, maxArraySize = 30;
while(testTimes-- > 0) {
Random r = new Random();
int size = r.nextInt(maxArraySize) + 1;
int[] array1 = new int[size], array2 = new int[size], array3 = new int[size];
for(int i = 0; i < size; ++i) array1[i] = array2[i] = array3[i] = r.nextInt(5000);
Arrays.sort(array1);
MergeSortRecursively.sort(array2);
MergeSortIteratively.sort(array3);
for(int i = 0; i < size; ++i) {
if(array1[i] != array2[i] || array1[i] != array3[i]) {
System.out.println("Oops!!, Not equals");
System.out.println("array:");
System.out.println(Arrays.toString(array1));
System.out.println("array2:");
System.out.println(Arrays.toString(array2));
System.out.println("array3:");
System.out.println(Arrays.toString(array3));
return;
}
}
System.out.println("Test case: " + testTimes + " pass");
}
System.out.println("Done Successfully!!");
}
}
|
5. Master公式
如果我们发现一个问题的时间复杂度$T(N)$和它的子问题的时间复杂度之间呈现这样的关系：
$$
T(N)=aT(\frac{N}{b}) + N^d
$$
那么$T(N)$是可以直接被算出来的，即：
$$ T(N) = \begin{cases}N^{max\{d,\log_b{a}\}}\quad \text{if}\log_b{a}\neq d; \\ N^d*\log_2{N}\quad \text{if} \log_b{a}= d; \end{cases} $$
这就是Master公式。
证明过程可以参考这里。
