首頁  >  文章  >  後端開發  >  php怎麼實作並歸排序

php怎麼實作並歸排序

藏色散人
藏色散人原創
2022-10-21 09:30:141091瀏覽

php實作並歸排序的方法:1、建立一個PHP範例檔;2、定義「public function handle(){...}」方法;3、透過「private function mergeSort($a, $lo, $hi) {...}」方法逐步分解資料;4、透過「merge」方法將分解後的資料排序,再合併到一起即可。

php怎麼實作並歸排序

php實作歸併排序演算法

歸併排序演算法的複雜度是O(nlogn)。

程式碼如下,只需clone下來執行composer install然後執行 php artisan test:mergeSort 就可以看到結果了

    /**
     * 归并排序把数据逐步分解,然后对分解后的数据进行排序,最后合并到一起
     *
     * @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(&#39;$b:&#39;,$b);
        //把中点右边的进行归并
        $c = $this->mergeSort($a, $mi, $hi);
        dump(&#39;$c:&#39;,$c);
        //把所有数据进行排序
        return $this->merge($b, $c, $lo,$mi,$hi);
    }
    /**
     * 假设有一个数组$a分成了两个数组[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数组的边界
        $lc = $hi - $mi; //$c数组的边界
        $res = [];
        //$i表示合并后数组的下标 $ib是b数组的下标 $ic是c数组的下标 
        for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
            //ib 下标没有越界 && c的数组已经空了也就是$ic >= $lc || 比较两个数组首位的大小 如果b的首元素 < c的首元素,那么取出来b的首元素
            if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
                $res[$i++] = $b[$ib++];
            }
            //k 下标没有越界 && b的数组已经空了也就是$ib >= $lb || 如果c的首元素 < b的首元素,那么取出来c的首元素 
            if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
                $res[$i++] = $c[$ic++];
            }
        }
        return $res;
    }

歸併排序原理

歸併排序和快排剛好相反,是先將整個數組左右打散,然後在逐一合併進行排序,最終完成整個數組的排序,排序示意圖如下:

php怎麼實作並歸排序

#首先將整個陣列左右打散,變成單一元素,因為單一元素可以被認為是有序的。

對應程式碼

if (($hi - $lo) < 2) return [$a[$lo]];
$mi = ($lo + $hi) >> 1;
//把中点左边的进行归并
$b = $this->mergeSort($a, $lo, $mi);
dump(&#39;$b:&#39;,$b);
//把中点右边的进行归并
$c = $this->mergeSort($a, $mi, $hi);
dump(&#39;$c:&#39;,$c);

接下來將左右兩個有序數組排序,假設有一個陣列$a分成了兩個陣列[3,4] [ 2,8],逐一比較,3and2,取出2然後3and8取出3然後4and8取出4,最後取出來8,對應代碼:

$lb = $mi - $lo; //$b数组的边界
$lc = $hi - $mi; //$c数组的边界
$res = [];
//$i表示合并后数组的下标 $ib是b数组的下标 $ic是c数组的下标 
for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
    //ib 下标没有越界 && c的数组已经空了也就是$ic >= $lc || 比较两个数组首位的大小 如果b的首元素 < c的首元素,那么取出来b的首元素
    if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
        $res[$i++] = $b[$ib++];
    }
    //k 下标没有越界 && b的数组已经空了也就是$ib >= $lb || 如果c的首元素 < b的首元素,那么取出来c的首元素 
    if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
        $res[$i++] = $c[$ic++];
    }
}
return $res;

示意圖如下:

php怎麼實作並歸排序


推薦學習:《PHP影片教學

以上是php怎麼實作並歸排序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn