PHP

PHP算法之归并排序

字号+ 编辑: Snake 修订: 小红帽 来源: 卓象科技 2023-09-07 我要说两句(0)

自带代码案例。

基本思想

归并排序的主要思想是分治法。

主要过程是:

1.将n个元素从中间切开,分成两部分。(左边可能比右边多1个数)

2.将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1。

3.从最底层开始逐步合并两个排好序的数列。

完整过程

首先我们看到,一个无序的数组如下,为了简约,以及简便解释,我们定义了8个元素。

1.jpg

然后,我们把该8个元素进行划分,分成左边四个,和右边四个

2.jpg

依次按照上边的方法,把剩余的数组继续拆分,一直拆到只剩下一个元素的时候,停止

3.jpg

由于存在8个单独的子元素,然后我们两两把元素合并,并且按照一定顺序排序

4.jpg

此时,我们可以看到我们又得到了四个不同颜色的数组,并且在这个数组里边,也是按照一定的顺序排好序的。随后,继续利用这种方法,把剩余的继续合并,一直合并到所有数都在一个数组里边。此时便是完成了合并。

5.jpg

整个过程(包括拆分和合并)如下:

6.jpg

代码如下:

// 归并排序主程序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";
阅完此文,您的感想如何?
  • 有用

    0

  • 没用

    0

  • 开心

    0

  • 愤怒

    0

  • 可怜

    0

1.如文章侵犯了您的版权,请发邮件通知本站,该文章将在24小时内删除;
2.本站标注原创的文章,转发时烦请注明来源;
3.交流群: PHP+JS聊天群

相关课文
  • mac开发接入微信公众号接口返回报错 cURL error 56: SSLRead() return error -9806

  • pecl安装程序时报错Array and string offset access syntax with curly braces is no longer supported

  • PHP的换行符是什么

  • 由于商家传入的H5交易参数有误,该笔交易暂时无法完成,请联系商家解决

我要说说
网上宾友点评
沙发已空