PHPでマージソートを実装する方法-PHPの問題-php.cn

マージソートを実装するための

php メソッド: 1. PHP サンプルファイルを作成します; 2. 「パブリック関数 handle(){...}」メソッドを定義します; 3. 「プライベート関数 mergeSort($a, $lo, $hi) {...}" メソッドを使用して、データを段階的に分解します。 4. "merge" メソッドを使用して、分解されたデータを並べ替えてから、それらをマージします。

PHPでマージソートを実装する方法

このチュートリアルの動作環境: Windows 7 システム、PHP バージョン 8.1、Dell G3 コンピューター。

php はマージソートアルゴリズムを実装します。

マージソートアルゴリズムの複雑さは O(nlogn) です。

コードは次のとおりです。クローンを作成して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('$b:',$b); //把中点右边的进行归并 $c = $this->mergeSort($a, $mi, $hi); dump('$c:',$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; }

ログイン後にコピー

マージソートの原理

マージソートはクイックソートの逆で、まず配列全体を左右に分割し、次に 1 つずつマージしてソートし、最後に配列全体のソートを完了します。ソート図は次のとおりです。

PHPでマージソートを実装する方法

最初に、配列全体を左右に分散して 1 つの要素にまとめます。これは、1 つの要素が順序付けされていると見なせるためです。

対応コード

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

ログイン後にコピー

次に、左右の順序配列をソートします。配列 $a が 2 つの配列 [3,4] [ 2, 8]、1 つずつ比較し、3 と 2、2 を取り出し、次に 3 と 8、3 を取り出し、次に 4 と 8、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でマージソートを実装する方法