ホームページ  >  記事  >  バックエンド開発  >  PHPソートアルゴリズムのマージソートの詳細解説 series_phpスキル

PHPソートアルゴリズムのマージソートの詳細解説 series_phpスキル

jacklove
jackloveオリジナル
2018-07-03 17:53:592148ブラウズ

この記事は主に PHP ソート アルゴリズム シリーズ Merge Sort の関連情報を詳しく紹介します。一定の参考値があります。興味のある方は

Merge Sort

を参照してください。

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

マージ プロセス

マージ ソートの核心は、2 つの順序付けされたシーケンスをマージする方法です。2 つの順序付けられた配列があると仮定し、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)

三次合併後

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


以上がこの記事の全内容です。皆様の学習に少しでもお役に立てれば幸いです。誰もがphp中国語ウェブサイトをサポートします。

#興味があるかもしれない記事:


PHP ソート アルゴリズム シリーズの直接選択ソートの詳細説明

PHPソートアルゴリズムシリーズの挿入ソートの詳細説明

バケットソートアルゴリズムのPHP実装解説


#

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

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。