PHPソートアルゴリズムシリーズのマージソートを詳しく解説-PHPチュートリアル-php.cn

PHPソートアルゴリズムシリーズのマージソートを詳しく解説

jacklove

リリース： 2023-03-27 14:54:01

オリジナル

1840 人が閲覧しました

PHPのソートアルゴリズムシリーズのマージソートについて詳しく解説した記事です。

マージソート

マージソート (MERGE-SORT) は、マージ操作に基づく効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法 (分割統治) の非常に典型的なアプリケーションです。すでに順序付けされているサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、まず各サブシーケンスを順序どおりにしてから、サブシーケンスセグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。

マージプロセス

マージソートの中心は、2 つの順序付けされた配列があると仮定し、どちらか小さい方の要素をマージします。それを 3 番目の配列に取り込んだ後、その要素は対応する配列から削除されます。同様に、配列に要素がない場合は、他の配列の残りの要素を 3 番目の配列の中央に直接追加できます。

原則

1. シーケンス内の 2 つの隣接する数値をすべて結合して ceil(n/2) シーケンスを形成します。ソート後、各シーケンスには 2 つの要素が含まれ、最後のシーケンスには 1 つの要素しか含まれません。

2. 上記のシーケンスを再度結合して ceil(n/4) シーケンスを形成します。各シーケンスには 4 つの要素が含まれており、最後のシーケンスには 3 つ以下の要素しか含まれません。

3. すべての要素が並べ替えられるまでステップ 2 を繰り返します。

例

配列 [53,89,12,6,98,25,37,92,5] をソートします

最初のマージ後

(53,89),12,(6,98) ,( 25,37),(5,92)

2回目のマージ後

(12,53,89),(6,25,37,98),(5,92)

3回目のマージ後

( 6,12,25,37,53,89,98),(5,92)

4回目の合併後

5,6,12,25,37,53,89,92,98

PHPコードの実装

function merge_sort($arr){
 
$length=count($arr);
 
if($length<=1){
 
return $arr;
 
}
 
//分解数组，递归排序
 
$half=ceil($length/2);
 
$arr2=array_chunk($arr,$half);
 
$left=merge_sort($arr2[0]);
 
$right=merge_sort($arr2[1]);
 
while(count($left)&&count($right)){
 
if($left[0]<$right[0]){
 
$reg[]=array_shift($left);
 
}else{
 
$reg[]=array_shift($right);
 
}
 
}
 
return array_merge($reg,$left,$right);
 
}

ログイン後にコピー

この記事では、PHP ソートアルゴリズムシリーズのマージソートについて詳しく説明しています。関連コンテンツについては、php 中国語の Web サイトを参照してください。