PHP でマージソートアルゴリズムを実装する手順の詳細な説明

今回は、PHP でマージ ソート アルゴリズムを実装する手順について詳しく説明します。PHP でマージ ソート アルゴリズムを実装するための 注意事項 について、実際のケースを見てみましょう。

基本的な考え方:

マージソート: マージ(結合)の考え方を用いて実装されたソート方法です。その原理は、最初のシーケンスに n 個の要素が含まれていると仮定すると、それを n 個の順序付きサブシーケンスと見なすことができ、各サブシーケンスの長さは 1 であり、ペアでマージして ⌈ n / 2⌉ (⌈ x ⌉ は最小値ではないことを意味します) を取得します。双方向マージソート未満の整数。

1. マージのプロセス:

a[i] は a 配列の前部分 (ソート済み) を受け取り、a[j] は a 配列 (ソート済み) の後ろの部分を受け取ります

r 配列storage ソートされた配列

は、a[i] と a[j] のサイズを比較します。 a[i] ≤ a[j] の場合、最初の順序付きリストの要素 a[i] を r [k] にコピーします。それ以外の場合は、2 番目の順序付けされたリストの要素 a[j] を r[k] にコピーし、j と k にそれぞれ 1 を追加するなど、順序付けされたリストの 1 つが完了するまで続けます。フェッチされ、他の順序付きリストの残りの要素を r の添字 k から添字 t までのセルにコピーします。通常、再帰を使用してマージ ソート アルゴリズムを実装します。まず、ソート対象の区間 [s, t] を中間点で 2 つに分割し、次に左側のサブ範囲をソートし、次に右側のサブ範囲をソートし、最後に を実行します。左側と右側の間隔でのマージ操作。順序付けされた間隔 [s,t] にマージします。

2. マージ操作:

マージ操作 (マージ) は、マージ アルゴリズムとも呼ばれ、2 つの連続したシーケンスを 1 つの連続したシーケンスにマージする方法を指します。

シーケンス {6, 202, 100, 301, 38, 8, 1} があるとします

初期状態: 6, 202, 100, 301, 38, 8, 1

最初のマージ後: {6,202} 、{100,301}、{8,38}、{1}、比較の数: 3;

2 回目のマージ後: {6,100,202,301}、{1,8,38}、比較の数: 4; 3 回目 マージ後: {1,6,8,38,100,202,301}、比較の数: 4;

比較の総数は: 3+4+4=11,;

逆数は 14 です。

3. アルゴリズムの説明:

マージ操作の動作原理は次のとおりです:

ステップ 1: サイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します。このスペースは、マージされたシーケンスを格納するために使用されます。シーケンス

ステップ 2: 2 つを設定します。ポインターの初期位置は、それぞれソートされた 2 つのシーケンスの開始位置です

ステップ 3: 2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージに入れますスペースを空けて、ポインタを次の位置に移動します

特定のポインタがシーケンスの末尾を超えるまで手順 3 を繰り返します

他のシーケンスの残りの要素をすべて、マージされたシーケンスの末尾に直接コピーします

アルゴリズムの実装:

まずメイン関数部分を見てみましょう:

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//归并算法总函数
function MergeSort(array &$arr){
  $start = 0;
  $end = count($arr) - 1;
  MSort($arr,$start,$end);
}

全体の関数では、再帰呼び出しを使用したいため、MSort() 関数を 1 つだけ呼び出しました。

MSort() 関数を見てみましょう:

function MSort(array &$arr,$start,$end){
  //当子序列长度为1时，$start == $end，不用再分组
  if($start < $end){
    $mid = floor(($start + $end) / 2); //将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
    MSort($arr,$start,$mid);  //将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
    MSort($arr,$mid + 1,$end);  //将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
    Merge($arr,$start,$mid,$end);    //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
  }
}

上記の MSort() 関数は、配列を半分に分割し、その後 (サブシーケンスまで) 半分に分割することを実装します。長さは 1 )、サブシーケンスをマージします。

MSort() 函数：

//归并操作
function Merge(array &$arr,$start,$mid,$end){
  $i = $start;
  $j=$mid + 1;
  $k = $start;
  $temparr = array();
  while($i!=$mid+1 && $j!=$end+1)
  {
    if($arr[$i] >= $arr[$j]){
      $temparr[$k++] = $arr[$j++];
    }
    else{
      $temparr[$k++] = $arr[$i++];
    }
  }
  //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($i != $mid+1){
    $temparr[$k++] = $arr[$i++];
  }
  //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($j != $end+1){
    $temparr[$k++] = $arr[$j++];
  }
  for($i=$start; $i<=$end; $i++){
    $arr[$i] = $temparr[$i];
  }
}

上面的 MSort() 函数实现将数组分半再分半（直到子序列长度为1），然后将子序列合并起来。

现在是我们的归并操作函数 Merge()次はマージ操作関数 Merge() です:

$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);

この時点で、マージ アルゴリズムは完了です。呼び出してみましょう:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

実行結果:

rrreee

複雑さの分析:

マージアルゴリズムは、元のシーケンスが順序付けされているかどうかに関係なく、グループ化して比較するため、その最良、最悪、平均の時間複雑さは O(nlogn) です。

マージアルゴリズムは安定した並べ替えアルゴリズムです。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

PHPシングルトンモードの使用例の詳細な説明

php+receivemailを使用してメールの送受信を行う

以上がPHP でマージソートアルゴリズムを実装する手順の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。