PHP 实现归并排序算法

栏目: PHP · 发布时间: 6年前

内容简介:下列动图来自利用递归,先拆后合并排。

算法原理

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

PHP 实现归并 <a href='https://www.codercto.com/topics/21904.html'>排序</a> 算法

原理:

利用递归,先拆后合并排。

步骤:

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

代码实现

// 归并排序主程序
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)

参考资料


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

淘宝、天猫网上开店速查速用一本通

淘宝、天猫网上开店速查速用一本通

刘珂 / 北京时代华文书局 / 2015-6 / 39.8

为了帮助众多的新手卖家掌握淘宝天猫网上开店、货源准备、店铺装修、商品拍摄、交易方法、营销推广以及售后服务等知识,本书作者根据自己多年网上开店心得,并结合了多名淘宝五皇冠店主和天猫旗舰店卖家的经验,精心策划编写了本书。 《淘宝、天猫网上开店速查速用一本通:开店、装修、运营、推广完全攻略》将目前最前沿、最流行的营销理念运用到淘宝天猫网上平台,所有技术都在实际应用获得显著效果,并且还在持续创造着惊......一起来看看 《淘宝、天猫网上开店速查速用一本通》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换