手记

常用的排序算法(四)--归并排序(PHP实现)

常用的排序算法系列


归并排序

假设当前需要从小到大进行排序,归并排序的核心思路是,把大的数组,不停地拆成小的数组,直到拆得最小,然后再把小数组两两排序合并,再将结果不停地进行一次次排序的合并。

归并排序本质上是一种分治算法的解法。

分治法的解法,就是对于一个规模较大的问题,将其分解为好多个规模较小的子问题,这些子问题的求解不会互相影响,并且与原问题形式相同。 然后递归地去求解解这些子问题,然后将各子问题的解,进行合并,得到原问题的解。

举例说明:

假设当前需要排序的数组如下:
[ 34, 5, 555,14, 88, 5 ]

拆分

我们要知道,拆分的目的是为了拆成更好求解的小数组。当数组长度为2的时候,我们只需要一次比较,就可以把这个小数组给排好序了。所以,我们拆分到的最小单位应该是2

首先我们需要拆分,找到数组的拆分中间位置,中点位置我们取长度一半的舍位整数。
数组长度是6,6/2 = 3 , 拆成左半边L1右半边L2
L1: [ 34, 5, 555 ]
L2: [ 14, 88, 5 ]

继续拆分,直到不能拆为止。先看左边L1。
L1数组长度是3,3/2=1.5≈1,拆成左半边L3右半边L4
L3: [ 34 ]
L4: [ 5, 555 ]

再继续,这时候L3,L4都是已经最小单位了,所以不用再拆了。

之后回头我们看右边L2。同理会被拆分成
L5: [ 14 ]
L6: [ 88, 5 ]

排序合并

每个子问题的得到的结果直接合并的时候会不会有问题呢?

例如,直接把 L3 和 L4 合并,会得到 [ 34, 5, 555 ]

诶,这就不对了,每个子问题求解得到的小数组,是不能直接合并的,所以这里也要做个小排序,进行排序地合并。

因此,可以很简单地,从前往后,每次从小数组里取出各自取出一个,把这两个数比较大小之后,再放进新的合并数组里。

比如 L3 取第一个是 34 ,L4 取第一个是 5 ,那么先放 5 进新数组里,再放 34。
L3取第二个,没有第二个,L4 取第二个是 555,那么再放 555。

L3: [ 34 ]
L4: [ 5, 555 ]

得到 L5 L6 的合并结果
L1’ :[ 5, 34 ,555 ]

同理,得到 L5 L6 的合并结果
L2’ : [ 5, 14, 88 ]

那么再继续合并,得到最终结果

各自取第一位,5 和 14,得 [ 5, 5 ]
取第二位,34 和 14 ,得 [ 5, 5, 14, 34 ]
取第三位,555 和 88 ,得 [ 5, 5, 14, 34, 88, 555 ]

这样就完成了整个过程。

具体的程序实现,归并排序可以通过递归来完成。通过一个循环,不断的切分左半部分与右半部分。切分的数组则不断地递归地调用排序函数。

如果切分出来的左右部分已经到了最小单位,那么就进行排序地合并,返回这个合并的结果。

PHP实现效果如下

PHP代码如下:

<?php
/**
 * Created by PhpStorm.
 * User: L
 * Date: 2018-9-27
 * Time: 15:33
 */


$ar = [5, 8, 6, 4, 12, 5, 3, 1, 89, 54];
echo "input: <br/>";
print_r(json_encode($ar));
echo "<br/>";
echo "<br/>";
$ar = merge($ar);
echo "result: <br/>";
print_r(json_encode($ar));
echo "<br/>";
echo "<br/>";

/** 归并排序 先拆左右 在两两合并
 * @param array $ar
 * @param null $len
 * @return array
 */
function merge(array $ar, $len = null)
{
    if ($len === null) {
        $len = sizeof($ar);
    }

    if ($len <= 1) {//len = 1 finish cuting
        return $ar;
    }
    //len>1 --> need sort and merge left and right
    //cut into 2 part -- left and right
    $mid = $mid = intval($len / 2);

    // 0 - mid xxxxx
    $left = array_slice($ar, 0, $mid);
    //  xxxx mid - end
    $right = array_slice($ar, $mid);

    echo "left:";
    print_r(json_encode($left));
    echo " -- right:";
    print_r(json_encode($right));
    echo "<br/>";

    $left = merge($left);//continue cut into 2 part until len = 1
    $right = merge($right);

    //get the smallest sorted unit to merge (len is decided by last function result)
    $merge = [];

    $len_left = sizeof($left);
    $len_right = sizeof($right);

    //init index, i for left ,j for right
    $i = $j = 0;
    //put left and right into merge by sorting
    while (sizeof($merge) < $len_left + $len_right) {

        if ($i < $len_left //still has left
            && ($j == $len_right || $left[$i] <= $right[$j])) { //right is over or left is smaller --> add left into merge
            $merge[] = $left[$i];
            $i++;

        } else if ($j < $len_right //still has right
            && ($i == $len_left || $left[$i] > $right[$j])) {//left is over or right is smaller --> add left into merge
            $merge[] = $right[$j];
            $j++;
        }
    }

    echo "  merge:";
    print_r(json_encode($merge));
    echo "<br/>";

    return $merge;

}

2人推荐
随时随地看视频
慕课网APP

热门评论

你上面的解释,难到没有问题吗

查看全部评论