归并排序的主要思想就是把数组不断分割，直到数组中只含1个元素的时候在一一合并，得到的新数组在合并的时候确保顺序。假设现在有数组arr，元素个数为n，那么可以分割为两个数组，0~n/2之间的元素作为新数组left，n/2+1到n-1之间的元素作为right数组。而left本身也是一个数组，又可以拆分为更小的left1和right1，同理，right也可以拆分，直到所有数组拆分到数组中只有一个元素（当元素个数为1，数组就必然有序）。然后进行合并操作，合并两个数组的时候，需要新建一个数组，从小到大依次取出元素，最终得到的新数组就是有序的，理解起来稍微复杂但实现起来比较简单，见代码
实现
Java实现（无空间优化的版本）
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
|
public static int[] mergeSort(int[] arr) {
if(arr.length == 1){
return arr;
}
int step = arr.length / 2;
int[] left = new int[step];
int[] right = new int[arr.length - step];
int index = 0;
for (int i = 0; i < left.length; i++) {
left[i] = arr[index];
index++;
}
for (int i = 0; i < right.length; i++) {
right[i] = arr[index];
index++;
}
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);
}
public static int[] merge(int[] left, int[] right) {
int[] arr = new int[left.length + right.length];
int i = 0, l = 0, r = 0;
while (l < left.length && r < right.length) {
if (left[l] <= right[r]) {
arr[i] = left[l];
i++;
l++;
} else {
arr[i] = right[r];
i++;
r++;
}
}
while (l < left.length) {
arr[i] = left[l];
i++;
l++;
}
while (r < right.length) {
arr[i] = right[r];
i++;
r++;
}
return arr;
}
|
上述代码会创建很多新数组存储临时变量，以下是优化后的代码，只需要一个大小为n的临时数组
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
|
public static void mergeSort(int[] arr, int[] tempArr, int left, int right) {
if (left < right) {
int mid = (right + left) / 2;
mergeSort(arr, tempArr, left, mid);
mergeSort(arr, tempArr, mid + 1, right);
merge(arr, tempArr, left, mid, right);
}
}
public static void merge(int[] arr, int[] tempArr, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
tempArr[i] = arr[i];
}
int i = left, l = left, r = mid + 1;
while (l <= mid && r <= right) {
if (tempArr[l] <= tempArr[r]) {
arr[i++] = tempArr[l++];
} else {
arr[i++] = tempArr[r++];
}
}
while (l <= mid) {
arr[i++] = tempArr[l++];
}
while (r <= right) {
arr[i++] = tempArr[r++];
}
}
|
归并排序将数组递归地分成两半，递归深度为 O(logn)。在每一层递归中，合并操作需要遍历所有 n 个元素，因此每层的时间复杂度为 O(n)。总时间复杂度为 O(nlogn)。无论输入数据是否有序，归并排序的比较次数和移动次数都是固定的，因此最好、最坏和平均时间复杂度均为 O(nlogn)。。由于需要额外数组，无优化版本（创建多个临时数组），空间复杂度为 O(nlogn)，优化版本需要一个大小为n的数组，因此空间复杂度为O(n)，这个排序的方式不会导致相同元素的左边元素交换到右边，所以这个算法是稳定的。
总结
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定