PHP 实现归并排序（Merge Sort）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP 实现归并排序（Merge Sort），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2705字，纯文字阅读大概需要4分钟。

内容图文

PHP 归并排序（Merge Sort）

归并排序 时间复杂度属于 O(nlogn) 级别的，相比于 O(n^2) 级别的排序算法，在处理大的数据量时，它的优势非常明显，下面通过原理图和代码演示介绍归并排序是如何实现 O(nlogn) 时间复杂度级别的。

1.将数组中有序的两部归并成一个过程原理图

在学习 归并排序 之前，先学习一下使用临时空间将数组中有序的两个部分归并成一个有序部分的原理图

Tips：需要额外使用空间，最后将排好序的值赋值给原来的变量中。

合并代码如下：

<?php
function twoMergeSort($arr,$left,$mid,$right){
    $aIndex = $left==$mid ? -1 : $left;
    $bIndex = $mid==$right ? -1 : $mid;
    $crr = [];

    while (($aIndex >= $left && $aIndex < $mid) || ($bIndex >= $mid && $bIndex <= $right)){
        $aValue = $arr[$aIndex]??null;
        $bValue = $arr[$bIndex]??null;
        if(($aIndex < $left || $aIndex >= $mid) || ($bValue < $aValue && $bValue != null)){
            $crr[] = $bValue;
            $bIndex++;
        }else{
            $crr[] = $aValue;
            $aIndex++;
        }
    }

    for ($i = 0;$i < ($right - $left);$i++){
        $arr[$i+$left] = $crr[$i];
    }

    return $arr;
}

$arr = [1,4,7,10,15,8,11,13,19,24];

print_r(twoMergeSort($arr,0,5,9));
/**
Array
(
    [0] => 1
    [1] => 4
    [2] => 7
    [3] => 8
    [4] => 10
    [5] => 11
    [6] => 13
    [7] => 15
    [8] => 19
    [9] => 24
)
 */

2. 无序数组分解示意图

可以使用递归二分的思想把一个无序的数组分解为多个单元素的数组（单元素数组也可以看做有序数组）

Tips：可以采用递归的思想实现归并排序。

3.归并排序代码

<?php
class MergeSort
{
    /**
     * 将数组两个有序部分合并成一个
     * @param $arr
     * @param $left
     * @param $mid
     * @param $right
     * @return mixed
     */
    private function twoMergeSort($arr,$left,$mid,$right){
        $aIndex = $left==$mid ? -1 : $left;
        $bIndex = $mid==$right ? -1 : $mid;
        $crr = [];

        while (($aIndex >= $left && $aIndex < $mid) || ($bIndex >= $mid && $bIndex <= $right)){
            $aValue = $arr[$aIndex]??null;
            $bValue = $arr[$bIndex]??null;
            if(($aIndex < $left || $aIndex >= $mid) || ($bValue < $aValue && $bValue != null)){
                $crr[] = $bValue;
                $bIndex++;
            }else{
                $crr[] = $aValue;
                $aIndex++;
            }
        }

        for ($i = 0;$i < ($right - $left);$i++){
            $arr[$i+$left] = $crr[$i];
        }
        return $arr;
    }


    public function arrayMergeSort($arr){
      $this->recursionMergeSort($arr,0,count($arr) - 1);
        return $arr;
    }

    private function recursionMergeSort($arr,$left,$right){
        if($left == $right){
            return;
        }

        $mid = ceil((($right - $left)/2) + $left);//($right + $left)/2 这种考虑内存溢出的优化

        $arr = $this->recursionMergeSort($arr,$left,$mid-1); //递归思想，交给下层处理排序
        $arr = $this->recursionMergeSort($arr,$mid,$right);//递归思想，交给下层处理排序
        $arr = $this->twoMergeSort($arr,$left,$mid,$right);//merge 两部有序内容
        return $arr;

    }
}

4.演示输出代码如下

<?php
//require 'merge_arr.php';
require 'MergeSort.php';

$mergeSort = new MergeSort();

print_r($mergeSort->arrayMergeSort([1,3,2,4,5,9,6,7,8]));

如下图所示:

5. O(nlogn) 和 O(n^2) 时间复杂度简单对比

代码仓库 ：https://gitee.com/love-for-poetry/data-structure

扫码关注爱因诗贤

内容总结

以上是互联网集市为您收集整理的PHP 实现归并排序（Merge Sort）全部内容，希望文章能够帮你解决PHP 实现归并排序（Merge Sort）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---