0%

归并排序

分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决,小的子问题解决了,大问题也就解决了。

一、概念

  1. 给定一个待排序数组,先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。
  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
function mergeSort($data)
{
$len = count($data);
if ($len <=1) {
return $data;
}

$middle = intval($len/2);
$left = mergeSort(array_slice($data, 0, $middle));
$right = mergeSort(array_slice($data, $middle));

$data = mergeArr($left, $right);
// $data = mergeArr1($left, $right);
return $data;
}

function mergeArr($arr1, $arr2)
{
$result = [];
// 合并两个数组的算法NB
while (count($arr1) && count($arr2)) {
$result[] = $arr1[0] < $arr2[0] ? array_shift($arr1) : array_shift($arr2);
}
return array_merge($result, $arr1, $arr2);
}

function mergeArr1($arr1, $arr2)
{
$i = 0;
$j = 0;
$result = array();
$len1 = count($arr1);
$len2 = count($arr2);

while ($i < $len1 && $j < $len2) {
if ($arr1[$i] < $arr2[$j]) {
$result[] = $arr1[$i];
$i++;
} else {
$result[] = $arr2[$j];
$j++;
}
}

while ($i < $len1) {
// $result[] = $arr1[$i++];
$result[] = $arr1[$i];
$i++;
}

while ($j < $len2) {
// $result[] = $arr2[$j++];
$result[] = $arr2[$j];
$j++;
}

return $result;
}