PHPのソートアルゴリズムのマージソートの詳細説明-PHPチュートリアル-php.cn

PHPのソートアルゴリズムのマージソートの詳細説明

小云云

リリース： 2023-03-19 11:08:02

オリジナル

1638 人が閲覧しました

PHP ソートアルゴリズムにはさまざまな種類があります。この記事では主に PHP ソートアルゴリズムシリーズの関連情報を詳しく紹介します。興味のある方は参考にしていただければ幸いです。

マージソート

マージソート (MERGE-SORT) は、マージ操作に基づく効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法 (pide と Conquer) を使用する非常に典型的なアプリケーションです。すでに順序付けされているサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、まず各サブシーケンスを順序どおりにしてから、サブシーケンスセグメントを順序どおりにします。 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コードの実装

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

ログイン後にコピー

皆さんは学びましたか？皆さんも早速試してみてください。