So implementieren Sie die Zusammenführungssortierung in PHP

So implementieren Sie die Zusammenführungssortierung in PHP: 1. Erstellen Sie eine PHP-Beispieldatei. 2. Definieren Sie die Methode „public function handle(){...}“. 3. Über „private function mergeSort($a, $lo, $ hi) {...}“-Methode, um die Daten schrittweise zu zerlegen; 4. Verwenden Sie die „merge“-Methode, um die zerlegten Daten zu sortieren und sie dann zusammenzuführen.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, PHP-Version 8.1, Dell G3-Computer.

php implementiert den Zusammenführungssortierungsalgorithmus

Die Komplexität des Zusammenführungssortierungsalgorithmus beträgt O(nlogn).

Der Code ist wie folgt, Sie müssen ihn nur klonen und ausführencomposer install然后执行 php artisan test:mergeSort und Sie können das Ergebnis sehen

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

Prinzip der Zusammenführungssortierung

Die Zusammenführungssortierung ist genau das Gegenteil der Schnellsortierung. Sie zerlegt zunächst das gesamte Array Vervollständigen Sie die Sortierung des gesamten Arrays wie folgt:

Verteilen Sie zunächst das gesamte Array nach links und rechts und verwandeln Sie es in ein einzelnes Element, da ein einzelnes Element als geordnet betrachtet werden kann.

Entsprechender Code

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

Als nächstes sortieren Sie die beiden geordneten Arrays links und rechts. Angenommen, es gibt ein Array $a, das in zwei Arrays [3,4] [2,8] unterteilt ist, und vergleichen Sie sie einzeln. 3und2 und nimm sie heraus 2 Dann nimm 3und8 heraus, 3 dann 4und8, nimm 4 heraus und nimm schließlich 8 heraus. Der entsprechende Code:

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

Das Diagramm lautet wie folgt:

Empfohlenes Lernen: „PHP-Video-Tutorial“

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Zusammenführungssortierung in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!