归并排序

发表于 | 分类于

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

一、概念

  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;
}