原创, 服务器

算法之 分治法/递归排序/归并排序 代码PHP版

先定义递归/分治/归并函数

function merge_sort($data = array(), $start = 0, $length = 0)
{
    if($length - $start > 1) {
        $middle = floor(($start + $length) / 2);
        $data = merge_sort($data, $start, $middle);
        $data = merge_sort($data, $middle, $length);
        $data = merge($data, $start, $middle, $length);
    }
    return $data;
}

function merge($data = array(), $start=0, $middle=0, $length=0)
{
    $left = $middle - $start;
    $right = $length - $middle;
    $array_left = array();
    $array_right = array();
    for($i = 0; $i < $left; $i++) {
        $array_left[$i] = $data[$start + $i];
    }
    for($j = 0; $j < $right; $j++) {
        $array_right[$j] = $data[$middle + $j];
    }
    $m = $n = 0;
    for($k = $start; $k < $length; $k++) {
        if( ! empty($array_left[$m]) && ! empty($array_right[$n])) {
            if($array_left[$m] <= $array_right[$n]) {
                $data[$k] = $array_left[$m];
                $m++;
            } else {
                $data[$k] = $array_right[$n];
                $n++;
            }
        } elseif ( ! empty($array_left[$m])) {
            $data[$k] = $array_left[$m];
            $m++;
        } else {
            $data[$k] = $array_right[$n];
            $n++;
        }
    }
    return $data;
}

调用方法

$result = merge_sort($data, 0, count($data))

返回一个升序的数组

时间复杂度 Θ(n lgn)

难点： 感觉到处是难点  虽然自己成功调试出正确结果，但总是感觉不能全部理解。

(368)

Related Post