PHP实现归并排序算法

<?php
    function merger_sort(&$arr,$frist,$end) {
        if($frist < $end) {
            $middle = floor(($frist+$end)/2);
            merger_sort($arr,$frist,$middle);
            merger_sort($arr,$middle+1,$end);
            merger($arr,$frist,$middle,$end);
        }
    }
    function merger(&$arr,$start,$mid,$end) {
        $i = $start;
        $j=$mid + 1;
        $k = $start;
        $temparr = array();

        while($i!=$mid+1 && $j!=$end+1)
        {
           if($arr[$i] >= $arr[$j]){
               $temparr[$k++] = $arr[$j++];
           }
           else{
               $temparr[$k++] = $arr[$i++];
           }
        }
        while($i != $mid+1){
            $temparr[$k++] = $arr[$i++];
        }

        while($j != $end+1){
            $temparr[$k++] = $arr[$j++];
        }

        for($i=$start; $i<=$end; $i++){
            $arr[$i] = $temparr[$i];
        }
    }

    function MergeSort(&$arr){
        $start = 0;
        $end = count($arr) - 1;
        merger_sort($arr,$start,$end);
    }
    $array = array(5,2,7,4);
    MergeSort($array);
    var_dump($array);

分治策略的步骤

  1. 分解 原问题为若干个子问题,这些子问题是原问题的规模较小的实例。
  2. 解决 这些子问题,递归地求解各子问题。然而子问题的规模足够小,则直接求解。
  3. 合并 这些子问题的解成原问题的解。

归并排序遵从分治策略

  1. merger_sort函数完成了分解的步骤,将原数组array(5,2,7,4)最终分解为array(5,2)和array(7,4)
  2. merger函数完成了解决(排序)和合并的操作首先对分解的array(5,2)和array(7,4)进行排序,得到 array(2,5)和array(4,7),然后合并为array(2,5,4,7),然后继续merge进行解决,流程是将2与4进行比较拿出较小的放在原数组中,然后将4和5进行比较,然后比较5和7,完成归并排序。

总结

归并排序的时间复杂度是o(nlogn)