Bagaimana untuk melaksanakan pengisihan gabungan dalam php

Cara melaksanakan pengisihan gabungan dalam PHP: 1. Cipta fail contoh PHP; , $lo, $hi) {...}" kaedah untuk menguraikan data secara beransur-ansur; 4. Gunakan kaedah "cantum" untuk mengisih data yang terurai dan kemudian menggabungkannya bersama-sama.

Persekitaran pengendalian tutorial ini: sistem Windows 7, PHP versi 8.1, komputer Dell G3.

php melaksanakan algoritma isihan cantuman

Kerumitan algoritma isihan cantum ialah O(nlogn).

Kod adalah seperti berikut, cuma klon dan laksanakan composer install dan kemudian laksanakan php artisan test:mergeSort untuk melihat hasilnya

    /**
     * 归并排序把数据逐步分解，然后对分解后的数据进行排序，最后合并到一起
     *
     * @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;
    }

Prinsip isihan gabungan

Gabung isihan dan cepat Isih adalah sebaliknya Keseluruhan tatasusunan pertama-tama bertaburan ke kiri dan kanan, dan kemudian digabungkan satu demi satu untuk mengisih Akhirnya, keseluruhan tatasusunan adalah seperti berikut:

< .

Kod sepadan

Seterusnya, susun tatasusunan tertib kiri dan kanan Katakan terdapat tatasusunan $a terbahagi kepada dua tatasusunan [3,4 ] [. 2,8], bandingkan satu demi satu, 3dan2, keluarkan 2, kemudian 3dan8, keluarkan 3, kemudian 4dan8, keluarkan 4, dan akhirnya keluarkan 8, kod yang sepadan:

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);

Rajah skematik adalah seperti berikut:

$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;

Pembelajaran yang disyorkan: "

Tutorial Video PHP

"

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pengisihan gabungan dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!