概述
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间。
效果图：
步骤
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
实例
原始数据：
3 5 2 6 2
归并的前提是将数组分开，一分为二，再一分为二，分到不能再分，进行归并。
第一轮分隔，索引2 ((0+4)/2=2) 为中间
|
1
|
[3 5 2] [6 2] |
第二轮分隔，对[3 5 2]进行分隔
|
1
|
[3 5] [2] [6 2] |
第三轮分隔，对[3 5]进行分隔
|
1
|
[3] [5] [2] [6 2] |
合并[3] [5]
|
1
|
[3 5] [2] [6 2] |
合并[3 5] [2]
|
1
|
[2 3 5] [6 2] |
第四轮分隔，对[6 2]进行分隔
|
1
|
[2 3 5] [6] [2] |
合并[6] [2]
|
1
|
[2 3 5] [2 6] |
合并[2 3 5] [2 6]
|
1
|
[2 2 3 5 6] |
代码实现(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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
package com.coder4j.main.arithmetic.sorting;public class Merge { private static int mark = 0; /** * 归并排序 * * @param array * @param low * @param high * @return */ private static int[] sort(int[] array, int low, int high) { int mid = (low + high) / 2; if (low < high) { mark++; System.out.println("正在进行第" + mark + "次分隔，得到"); System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]"); // 左边数组 sort(array, low, mid); // 右边数组 sort(array, mid + 1, high); // 左右归并 merge(array, low, mid, high); } return array; } /** * 对数组进行归并 * * @param array * @param low * @param mid * @param high */ private static void merge(int[] array, int low, int mid, int high) { System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]"); int[] temp = new int[high - low + 1]; int i = low;// 左指针 int j = mid + 1;// 右指针 int k = 0; // 把较小的数先移到新数组中 while (i <= mid && j <= high) { if (array[i] < array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // 两个数组之一可能存在剩余的元素 // 把左边剩余的数移入数组 while (i <= mid) { temp[k++] = array[i++]; } // 把右边边剩余的数移入数组 while (j <= high) { temp[k++] = array[j++]; } // 把新数组中的数覆盖array数组 for (int m = 0; m < temp.length; m++) { array[m + low] = temp[m]; } } /** * 归并排序 * * @param array * @return */ public static int[] sort(int[] array) { return sort(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("最终结果"); for (int i : sorted) { System.out.print(i + " "); } }} |
测试输出结果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
正在进行第1次分隔，得到[0-2] [3-4]正在进行第2次分隔，得到[0-1] [2-2]正在进行第3次分隔，得到[0-0] [1-1]合并:[0-0] 和 [1-1]合并:[0-1] 和 [2-2]正在进行第4次分隔，得到[3-3] [4-4]合并:[3-3] 和 [4-4]合并:[0-2] 和 [3-4]最终结果2 2 3 5 6 |
经测试，与实例中结果一致。
