简介

归并排序(Merge sort)，是创立在归并操作上的一种无效的排序算法，其工夫复杂度为O(N*logN)。该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用，且各层分治递归能够同时进行。

归并排序算法应用了分而治之的思维：

  • 分：在数组的两头地位，将数组一分为二，将原数组排序的问题转换为排序两个子数组的问题；
  • 治：直到子数组的长度为 1 时，开始向上合并，一直地将两个曾经排序了的子数组归并成一个有序数组，直至归并至失去原数组的解。

实现思路

  1. 递归：

    1. 计算中点的地位 mid，将数组一分为二，并对这两个子数组递归解决，即 mergeSort(arr, l, mid)；mergeSort(arr, mid+1, r)；
    2. 直到 l >= r 时进行递归。

  2. 合并

    1. 暂存 arr 中区间 [l, r] 的元素到长期数组中；

    2. 合并左右子数组：

      • 循环遍历长期数组 temp；
      • 用 i 和 j 别离指向左右子数组的第一个元素，用 k 指向原数组中 l 的地位；
      • 当 i 大于左子数组的右边界时，阐明左子数组的元素曾经归并实现，因而增加 temp[j - l]，并执行 j++；
      • 当 j 大于右子数组的右边界时，阐明右子数组的元素曾经归并实现，因而增加 temp[i - l]，并执行 i++；
      • 当 temp[i - l] <= temp[j - l] 时，增加 temp[i - l]，并执行 i++；
      • 否则增加 temp[j - l]，并执行 j++；

须要留神的是：

  • 长期数组 temp 的索引是从 0 到 r - l 的；
  • 在循环遍历长期数组时，应该先判断 i 和 j 是否出界，再判断 i 和 j 所指向的元素哪个大。

例子

对数组 [5 , 3, 1, 2, 4, 7, 8, 2] 进行归并排序的过程：

归并

已知两个有序数组 arr1 和 arr2 别离为 [1, 2, 4]、[3, 5]，如何把这两个有序数组归并成一个有序数组？

<?phpfunction mergeSortedArr($arr1, $arr2){    $arr = [];    $len1 = count($arr1);    $len2 = count($arr2);    $len = $len1 + $len2;    $k = $i = $j = 0;    while($k < $len) {        if ($i >= $len1 ) {            $arr[] = $arr2[$j];            $j ++;        } elseif ($j >= $len2) {            $arr[] = $arr1[$i];            $i++;        } elseif ($arr1[$i] <= $arr2[$j]) {            $arr[] = $arr1[$i];            $i ++;        } elseif ($arr1[$i] > $arr2[$j]) {            $arr[] = $arr2[$j];            $j ++;        }        $k ++;    }    return $arr;}

已知一个数组在区间 [0, mid] 和 [mid+1, len - 1] 都是有序的，其中 len 为数组的长度，即 len = count(arr)； mid 为数组的两头地位，即 mid = floor(len / 2)。例如数组 arr 为 [1, 2, 4, 3, 5]，其中 mid 和 len 的值别离为：

  • len = count(arr) = 5;
  • mid = floor(5 / 2) = 2;

能够看出数组 arr 在区间 [0, 2] 是有序的，即子数组 [1, 2, 4] 是有序的，在区间 [3, 4] 是有序的，即子数组 [3, 5] 是有序的。问如何把 arr 变成一个有序的数组？

<?phpfunction merge($arr, $l, $mid, $r){    $temp = copyOfRange($arr, $l, $r + 1);    $i = $l;    $j = $mid + 1;    for ($k = $l; $k <= $r; $k++) {        if ($i > $mid) {            $arr[$k] = $temp[$j - $l];            $j ++;        } elseif ($j > $r) {            $arr[$k] = $temp[$i - $l];            $i ++;        } elseif ($temp[$i - $l] <= $temp[$j - $l]) {            $arr[$k] = $temp[$i - $l];            $i ++;        } else {            $arr[$k] = $temp[$j - $l];            $j ++;        }    }    return $arr;}function copyOfRange($arr, $l, $r){    $temp = [];    for ($i = $l; $i < $r; $i++) {        $temp[] = $arr[$i];    }    return $temp;}

代码

<?phpclass MergeSort{    public function sort(&$arr)    {        $this->implementSort($arr, 0, count($arr) - 1);    }    protected function implementSort(&$arr, $l, $r)    {        if ($l >= $r) {            return;        }        $mid = floor(($l + $r)/2);        $this->implementSort($arr, $l, $mid);        $this->implementSort($arr, $mid+1, $r);        $this->merge($arr, $l, $mid, $r);    }    protected function merge(&$arr, $l, $mid, $r)    {        $temp = $this->copyOfRange($arr, $l, $r + 1);        $i = $l;        $j = $mid + 1;        for ($k = $l; $k <= $r; $k++) {            if ($i > $mid) {                $arr[$k] = $temp[$j - $l];                $j ++;            } elseif ($j > $r) {                $arr[$k] = $temp[$i - $l];                $i ++;            } elseif ($temp[$i - $l] <= $temp[$j - $l]) {                $arr[$k] = $temp[$i - $l];                $i ++;            } else {                $arr[$k] = $temp[$j - $l];                $j ++;            }        }    }    protected function copyOfRange($arr, $l, $r)    {        $temp = [];        for ($i = $l; $i < $r; $i++) {            $temp[] = $arr[$i];        }        return $temp;    }}

优化

  • 优化1：判断是否须要 merge；
  • 优化2：对小规模数据应用插入排序；
  • 优化3：只创立一个长期空间。

自底向上

当前有工夫再回来补上。

变式

剑指 Offer 51. 数组中的逆序对：

在数组中的两个数字，如果后面一个数字大于前面的数字，则这两个数字组成一个逆序对。输出一个数组，求出这个数组中的逆序对的总数。

示例：

输出: [7,5,6,4]输入: 5

限度：

0 <= 数组长度 <= 50000

这道题是逆序排序的变式，它不间接考逆序排序怎么写，而是考查解题人对逆序排序过程的相熟水平。

参考

  1. 【算法】排序算法之归并排序
  2. 「排序算法」归并排序