归并排序利用归并（合并）的思想实现的排序方法。它的原理是假设初始序列含有 n 个元素，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 n / 2 个长度为 2 或 1 的有序序列；再两两归并，……，如此重复，直至得到一个长度为 n 的有序序列为止，这种排序方法就成为两路归并排序。
概念
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。在归并操作中将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
实现
方案一
递归法 - Top-down：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
| <?php
class MergeSort
{
/**
* 主运行方法。
*
* @return void
*/
public static function main(): void
{
$random = self::random();
$array = self::sort($random, 0, count($random) - 1);
print_r($array);
}
/**
* 归并排序。
*
* @param array $array
* @param int $left
* @param int $right
*
* @return array
*/
public static function sort(array &$array, int $left, int $right): array
{
if ($left < $right) {
$middle = (int)floor($left + $right) / 2;
self::sort($array, $left, $middle);
self::sort($array, $middle + 1, $right);
self::merge($array, $left, $middle, $right);
}
return $array;
}
/**
* 合并数组。
*
* @param array $array
* @param int $left
* @param int $middle
* @param int $right
*
* @return void
*/
private static function merge(array &$array, int $left, int $middle, int $right): void
{
$i = $left;
$j = $middle + 1;
$k = $left;
$tmp = [];
while ($i <= $middle && $j <= $right) {
if (self::compare($array[$i], $array[$j]) > 0) {
$tmp[$k++] = $array[$j++];
} else {
$tmp[$k++] = $array[$i++];
}
}
while ($i <= $middle) {
$tmp[$k++] = $array[$i++];
}
while ($j <= $right) {
$tmp[$k++] = $array[$j++];
}
for ($k = $left; $k <= $right; $k++) {
$array[$k] = $tmp[$k];
}
}
/**
* 比较大小。
*
* @param int $x
* @param int $y
*
* @return int
*/
private static function compare(int $x, int $y): int
{
return $x <=> $y;
}
/**
* 互换位置。
*
* @param int $x
* @param int $y
*
* @return void
*/
private static function swap(int &$x, int &$y): void
{
if ($x !== $y) {
$t = $x;
$x = $y;
$y = $t;
}
}
/**
* 生成随机数组。
*
* @param int $low
* @param int $high
* @param int $num
*
* @return array
*/
private static function random(int $low = 1, int $high = 9999, int $num = 10): array
{
$num = $num > $high ? $high : $num;
$range = range($low, $high);
$array = array_rand(array_flip($range), $num);
shuffle($array);
return $array;
}
}
MergeSort::main();
// 结果
Array
(
[0] => 1167
[1] => 2750
[2] => 3331
[3] => 4187
[4] => 4526
[5] => 5246
[6] => 5325
[7] => 6238
[8] => 7737
[9] => 9883
)
|
由于 PHP 具备数组分割和数组合并这样的函数，所以以上的实现可以更加简单
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| <?php
class MergeSort
{
/**
* 主运行方法。
*
* @return void
*/
public static function main(): void
{
$random = self::random();
$array = self::sort($random);
print_r($array);
}
/**
* 归并排序。
*
* @param array $array
*
* @return array
*/
public static function sort(array &$array): array
{
$count = count($array);
if ($count <= 1) {
return $array;
}
// 向上取整。
$middle = ($count >> 1) + ($count & 1);
$chunk = array_chunk($array, $middle);
$left = self::sort($chunk[0]);
$right = self::sort($chunk[1]);
$arr = [];
while (count($left) && count($right)) {
if (self::compare($left[0], $right[0]) > 0) {
$arr[] = array_shift($right);
} else {
$arr[] = array_shift($left);
}
}
return array_merge($arr, $left, $right);
}
/**
* 比较大小。
*
* @param int $x
* @param int $y
*
* @return int
*/
private static function compare(int $x, int $y): int
{
return $x <=> $y;
}
/**
* 互换位置。
*
* @param int $x
* @param int $y
*
* @return void
*/
private static function swap(int &$x, int &$y): void
{
if ($x !== $y) {
$t = $x;
$x = $y;
$y = $t;
}
}
/**
* 生成随机数组。
*
* @param int $low
* @param int $high
* @param int $num
*
* @return array
*/
private static function random(int $low = 1, int $high = 9999, int $num = 10): array
{
$num = $num > $high ? $high : $num;
$range = range($low, $high);
$array = array_rand(array_flip($range), $num);
shuffle($array);
return $array;
}
}
MergeSort::main();
// 结果
Array
(
[0] => 1281
[1] => 1337
[2] => 3213
[3] => 4078
[4] => 5350
[5] => 5857
[6] => 5889
[7] => 8088
[8] => 8190
[9] => 8440
)
|
方案二
迭代法 - Bottom-up：
- 将序列每相邻两个数字进行归并操作，形成
ceil(n/2) 个序列，排序后每个序列包含两/一个元素 - 若此时序列数不是
1 个则将上述序列再次归并，形成 ceil(n/4) 个序列，每个序列包含四/三个元素 - 重复步骤
2，直到所有元素排序完毕，即序列数为 1