归并排序算法

2017-03-02 13:24 Posted in Learn with PHP , algorithm

归并排序是分而治之思路的一个典型应用。

首先考虑如何合并两个有序数组的问题，这个非常简单，只要分别先对比两个数组第一个元素的大小，先把小的放入结果数组，再把它从原数组中删除，再把大的放入结果数组，从原数组中删除，之后再对比第二个元素..以此类推，如果其中一个数组为空，那就把另外一个数组中全部的元素放入结果数组。

那么如果是给一个无序数组要求排序呢？我们可以先把这个无序数组从中断开，一分为二，再分别把这两个数组二分为四，这样一直分下去，等得到只有一个元素的数组时，我们就认为这个单元素数组是有序的。之后再利用上面提到的算法把相邻两个数组合并起来就行了。这就是归并算法的概念。

那么下面上代码来实现：

<?php
function divide(array $arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $left = $right = array();
    $middle = round(count($arr)/2);
    for ($i = 0; $i < $middle; $i++) {
        $left[] = $arr[$i];
    }
    for ($i = $middle; $i < count($arr); $i++) {
        $right[] = $arr[$i];
    }
    $left = divide($left);
    $right = divide($right);
    return conquer($left, $right);
}
 
function conquer(array $left, array $right) {
    $result = array();
    while (count($left) > 0 || count($right) > 0) {
        if (count($left) > 0 && count($right) > 0) {
            $firstLeft = current($left);
            $firstRight = current($right);
            if ($firstLeft <= $firstRight) {
                $result[] = array_shift($left);
            } else {
                $result[] = array_shift($right);
            }
        } else if (count($left) > 0) {
            $result[] = array_shift($left);
        } else if (count($right) > 0) {
            $result[] = array_shift($right);
        }
    }
    return $result;
}

可以看到，归并排序的时间复杂度在divide()处是O(log*n)的，而在conquer处是O(n)，两相结合最后的时间复杂度就是O(nlogn)，并且表现比快速排序更好。

BlueBreeze

Blog

归并排序算法