PHP 实现归并排序算法

逃离我推掉我的手 2022-03-07 15:38 151阅读 0赞

## 算法原理 ##

下列动图来自**@五分钟学算法**，演示了归并算法的原理和步骤。

![merge][]

**原理:**

> 利用递归，先拆分、后合并、再排序。

**步骤:**

*  均分数列为两个子数列
 *  递归重复上一步骤，直到子数列只有一个元素
 *  父数列合并两个子数列并排序，递归返回数列

## 代码实现 ##

// 归并排序主程序
    function mergeSort($arr) {
        $len = count($arr);
        if ($len <= 1) {
            return $arr;
        } // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组
    
        $mid = intval($len / 2); // 取数组中间
        $left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left
        $right = array_slice($arr, $mid); // 拆分数组mid-末尾这部分给右边right
        $left = mergeSort($left); // 左边拆分完后开始递归合并往上走
        $right = mergeSort($right); // 右边拆分完毕开始递归往上走
        $arr = merge($left, $right); // 合并两个数组,继续递归
    
        return $arr;
    }
    
    // merge函数将指定的两个有序数组(arrA, arr)合并并且排序
    function merge($arrA, $arrB) {
        $arrC = array();
        while (count($arrA) && count($arrB)) {
            // 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值,
            // 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用
            $arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
        }
    
        return array_merge($arrC, $arrA, $arrB);
    }

测试:

$startTime = microtime(1);
    
    $arr = range(1, 10);
    shuffle($arr);
    
    echo "before sort: ", implode(', ', $arr), "\n";
    $sortArr = mergeSort($arr);
    echo "after sort: ", implode(', ', $sortArr), "\n";
    
    echo "use time: ", microtime(1) - $startTime, "s\n";

## 时间复杂度 ##

归并排序的时间复杂度是 `O(N*lgN)`。

假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 `O(N)`，需要遍历多少次呢？

归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是 `O(N*lgN)`。

## 参考资料 ##

*  [归并排序][Link 1]
 *  [十大经典排序算法动画与解析][Link 2]

--------------------

感谢您的阅读，觉得内容不错，点个赞吧 ?

> 原文地址: [https://shockerli.net/post/me...][https_shockerli.net_post_me...]

[merge]: https://image-static.segmentfault.com/330/904/3309043775-5c6b6605645a1_articlex
[Link 1]: http://www.cnblogs.com/skywang12345/p/3602369.html
[Link 2]: https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg
[https_shockerli.net_post_me...]: https://shockerli.net/post/merge-sort-implement-by-php?source=segmentfault