您现在的位置是:网站首页>>PHP>>php

php 实现归并排序

发布时间:2019-02-19 15:30:39作者:wangjian浏览量:247点赞量:0

    之前我总结过一些php排序方法:php 数组排序 ,今天我看到了一个名为归并排序的算法,感觉比较有意思,就研究了一下

    参考资料:https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg

    1:归并排序演示(资料来自上述地址)

    640.gif

    2:实例:

    <?php
    // 归并排序
    function mergeSort($arr) {
        $len = count($arr);
        //数组就只有一个元素时,直接返回
        if ($len <= 1) {
            return $arr;
        } 
        $mid = intval($len / 2); // 取数组中间
        $left = array_slice($arr, 0, $mid); //数组拆分,以0下标开始,长度为$mid拆分
        $right = array_slice($arr, $mid); // 数组拆分,以$mid下标开始到数组结尾拆分
        $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);//array_shift():删除数组中第一个元素,并返回被删除元素的值
        }
        return array_merge($arrC, $arrA, $arrB);
    }
    $arr = range(1,10);
    shuffle($arr);//将数组随机重组
    echo "before sort: ", implode(', ', $arr), "<br/>";
    $sortArr = mergeSort($arr);
    echo "after sort: ", implode(', ', $sortArr), "<br/>";

    现象如下:

    image.png


0 +1