php如何實現(xiàn)并歸排序

今天小編給大家分享一下php如何實現(xiàn)并歸排序的相關(guān)知識點，內(nèi)容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

php實現(xiàn)并歸排序的方法：1、創(chuàng)建一個PHP示例文件；2、定義“public function handle(){...}”方法；3、通過“private function mergeSort($a, $lo, $hi) {...}”方法把數(shù)據(jù)逐步分解；4、通過“merge”方法對分解后的數(shù)據(jù)進行排序，再合并到一起即可。

php實現(xiàn)歸并排序算法

歸并排序算法的復(fù)雜度是O(nlogn)。

代碼如下,只需要clone下來執(zhí)行composer install然后執(zhí)行 php artisan test:mergeSort 就可以看到結(jié)果了

    /**
     * 歸并排序把數(shù)據(jù)逐步分解，然后對分解后的數(shù)據(jù)進行排序，最后合并到一起
     *
     * @return mixed
     */
    public function handle()
    {
        $this->a = [3,70,4,38,5,6,8,4,7,10,6,10,34,4];
        dump($this->a);
        $a = $this->mergeSort($this->a, 0, count($this->a));
        dd($a);
    }
    private function mergeSort($a, $lo, $hi) {
        if (($hi - $lo) < 2) return [$a[$lo]];
        $mi = ($lo + $hi) >> 1;
        //把中點左邊的進行歸并
        $b = $this->mergeSort($a, $lo, $mi);
        dump('$b:',$b);
        //把中點右邊的進行歸并
        $c = $this->mergeSort($a, $mi, $hi);
        dump('$c:',$c);
        //把所有數(shù)據(jù)進行排序
        return $this->merge($b, $c, $lo,$mi,$hi);
    }
    /**
     * 假設(shè)有一個數(shù)組$a分成了兩個數(shù)組[3,4] [2,8]
     * 逐一比較，3and2，取出來2然后3and8取出來3然后4and8取出來4，最后取出來8
     *
     * @param [type] $lo
     * @param [type] $mi
     * @param [type] $hi
     * @return void
     */
    private function merge($b, $c, $lo, $mi, $hi) {
        $lb = $mi - $lo; //$b數(shù)組的邊界
        $lc = $hi - $mi; //$c數(shù)組的邊界
        $res = [];
        //$i表示合并后數(shù)組的下標(biāo) $ib是b數(shù)組的下標(biāo) $ic是c數(shù)組的下標(biāo) 
        for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
            //ib 下標(biāo)沒有越界 && c的數(shù)組已經(jīng)空了也就是$ic >= $lc || 比較兩個數(shù)組首位的大小 如果b的首元素 < c的首元素，那么取出來b的首元素
            if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
                $res[$i++] = $b[$ib++];
            }
            //k 下標(biāo)沒有越界 && b的數(shù)組已經(jīng)空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那么取出來c的首元素 
            if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
                $res[$i++] = $c[$ic++];
            }
        }
        return $res;
    }

歸并排序原理

歸并排序和快排剛好相反，是先將整個數(shù)組左右打散，然后在逐一合并進行排序，最終完成整個數(shù)組的排序，排序示意圖如下：

首先將整個數(shù)組左右打散，變成單個元素，因為單個元素可以被認(rèn)為是有序的。

對應(yīng)代碼

if (($hi - $lo) < 2) return [$a[$lo]];
$mi = ($lo + $hi) >> 1;
//把中點左邊的進行歸并
$b = $this->mergeSort($a, $lo, $mi);
dump('$b:',$b);
//把中點右邊的進行歸并
$c = $this->mergeSort($a, $mi, $hi);
dump('$c:',$c);

接下來對左右兩個有序數(shù)組進行排序，假設(shè)有一個數(shù)組$a分成了兩個數(shù)組[3,4] [2,8]，逐一比較，3and2，取出來2然后3and8取出來3然后4and8取出來4，最后取出來8，對應(yīng)代碼：

$lb = $mi - $lo; //$b數(shù)組的邊界
$lc = $hi - $mi; //$c數(shù)組的邊界
$res = [];
//$i表示合并后數(shù)組的下標(biāo) $ib是b數(shù)組的下標(biāo) $ic是c數(shù)組的下標(biāo) 
for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
    //ib 下標(biāo)沒有越界 && c的數(shù)組已經(jīng)空了也就是$ic >= $lc || 比較兩個數(shù)組首位的大小 如果b的首元素 < c的首元素，那么取出來b的首元素
    if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
        $res[$i++] = $b[$ib++];
    }
    //k 下標(biāo)沒有越界 && b的數(shù)組已經(jīng)空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那么取出來c的首元素 
    if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
        $res[$i++] = $c[$ic++];
    }
}
return $res;

示意圖如下：

以上就是“php如何實現(xiàn)并歸排序”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。