PHP 算法 —— 归并排序

leoperfect 发布于2019-07-01 11:20 / 2872人阅读

摘要：算法原理下列动图来自五分钟学算法，演示了归并算法的原理和步骤。原理利用递归，先拆分后合并再排序。假设被排序的数列中有个数。参考资料归并排序十大经典排序算法动画与解析感谢您的阅读，觉得内容不错，点个赞吧

算法原理

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

原理:

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

步骤:

均分数列为两个子数列

递归重复上一步骤，直到子数列只有一个元素

父数列合并两个子数列并排序，递归返回数列

代码实现

// 归并排序主程序
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), "
";
$sortArr = mergeSort($arr);
echo "after sort: ", implode(", ", $sortArr), "
";

echo "use time: ", microtime(1) - $startTime, "s
";

时间复杂度

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

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

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

参考资料

归并排序

十大经典排序算法动画与解析

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

私有云 GPU服务器归并排序算法 php的归并排序归并排序二路归并排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/30108.html

PHP面试：尽可能多的说出你知道的排序算法

摘要：良好的排序算法具有进行最少的比较和交换的特征。冒泡排序是一个基于比较的排序算法，被认为是效率最低的排序算法之一。现在让我们使用实现冒泡排序算法。插入排序到目前为止，我们已经看到了两种基于比较的排序算法。预警本文适合对于排序算法不太了解的新手同学观看，大佬直接忽略即可。因为考虑到连贯性，所以篇幅较长。老铁们看完需要大概一个小时，但是从入门到完全理解可能需要10个小时(哈哈哈，以我自己...

objc94 2019-07-01 10:39 评论0 收藏0
PHP面试之四：逻辑与算法

摘要：数据结构常见数据结构数组是最简单而且应用最广泛的数据结构特征使用连续内存空间来存储存放相同类型或着衍生类型的元素数组比较特别，可以存放八种数据类型通过下标来访问集合特征保存不重复的元素字典特征就是关联数组，以形式存储栈，与队列相似特征存储数数据结构常见数据结构 Array 数组是最简单而且应用最广泛的数据结构特征： 1、使用连续内存空间来存储 2、存放相同类型或着衍生类型...

smartlion 2019-06-28 14:11 评论0 收藏0
归并排序 - Algorithms, Part I, week 3 MERGESORTS

摘要：两个单元素数组的合并实际就是对这两个数进行了排序，即变为，同样再对后一组的两个数归并排序，即变为，再将两单元数组归并成四单元数组即和归并为。前言本周讲解两个50多年前发明，但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 -- 归并排序，几乎每个软件系统中都可以找到其中一个或两个的实现，并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法...

Jokcy 2019-08-19 11:35 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 评论0 收藏0