归并排序

概念

归并排序（也可以称之为合并排序）是一种基于O (n log n)比较的排序算法。大多数实现都会产生一个稳定的排序，这意味着实现在排序后的输出中保留相等元素的输入顺序。

步骤

先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了

解法

• 整体分为拆分和合并。拆分使用递归，设置高低指针 $low = 0，$height = len-1; 找出中间点 mind = $low + floor(($height-$low)/2)，
• 一直递归拆分，每个都拆分为：低到中间，中间到高；直至指针相遇。
• 然后从小到大进行合并。合并是将拆分(合并好相对有序)的两部分合并为有序的一部分，方便进行最后的合并。
• merageArr($arr,$low,$mind,$height) 此时使用两个指针 $i 和 $j 从头开始比较两个有序数列，$i = $start,$j = $min+1。
• 设置一个临时数组用来存放最后的结果，在$i $j范围内进行比较(i<=min.j<=end)，将小的元素放入数组，相应的i或者j +1，
• 最后将未参与比较的序列剩余元素(i < min + 1 ,j < end +1)放入数组中，合并完成。
• 最后讲临时数组放回数组中。
• 注意：递归公式 merge_sort(p..r) = merge(merge_sort(p..mind) ,merge_sort(mind+1..r))
• 终止条件 low < height
• 合并时：最后将未参与比较的序列剩余元素(i < min + 1 ,j < end +1)放入数组中,然后使用临时数组替换目标数组

实例（并非每个步骤都是按照如上的解法实现。使用了array_shift函数）

/**
 * 归并排序
 *
 * @param  array  $arr
 */
static function mergeSort(array &$arr)
{
    if (empty($arr) || count($arr) == 1) return;

    $middle = ceil(count($arr) / 2);

    // 切分左右两个区间

    $left = array_slice($arr, 0, $middle);

    $right = array_slice($arr, $middle);

    // 左区间做主区间，继续切分，直至左右两侧各自为单一的数据
    self::mergeSort($left);

    // 右区间做主区间，继续切分，直至左右两侧各自为单一的数据
    self::mergeSort($right);

    $temp = [];

    // 左右区间对比排序，并合并数组
    $merge = self::mergeByMergeSort($left, $right);

    $arr = array_merge($temp, $merge);
}

static function mergeByMergeSort($left, $right)
{
    // array_shift 删除数组中的第一个元素，并返回被删除元素的值

    $temp = [];
    // 如果左右都存在值，判断大小
    while ($left && $right)
    {
        $temp[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
    }
    // 如果只有左侧有数据
    while ($left)
    {
        $temp[] = array_shift($left);
    }
    // 如果只有右侧有数据
    while ($right)
    {
        $temp[] = array_shift($right);
    }

    return $temp;
}