ホームページ >バックエンド開発 >PHPの問題 >PHP 配列 - マージソートの使用方法?

PHP 配列 - マージソートの使用方法?

慕斯
慕斯オリジナル
2021-06-24 16:28:121254ブラウズ

私たちは PHP の配列についてはよく知っています。マージ ソートについてはどれくらい知っているかわかりません。この部分の知識は多くの人が知らないと思います。だから心配しないでください。この記事を読むと、より深い理解が得られます。

関連する推奨事項: PHP 配列の検索アルゴリズムとは何ですか?どうやって見つけますか?

マージ ソート:

マージ ソート (ERGE-SOQfT) は、マージ操作に基づいた効果的な並べ替えアルゴリズムです。このアルゴリズムは、非常に典型的なアプリケーションを使用します。分割統治。すでに順序付けられているサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序どおりにしてから、サブシーケンス セグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。コードを例として見てみましょう:

<?php
//PHP数组排序算法:合并算法.
//二路归并
$arr1 = array(1,3,5);
$arr2 = array(2,4,6);
//取出一个空数组用于归并空间
$arr3 = array();
while(count($arr1) & count($arr2)){
//只要$arr1和$arr2里面还有元素,就进行循环
//取出每个数组的第-一个元素:进行比较
$arr3[] = $arr1[0] < $arr2[0] ? array_shift($arr1) : array_shift($arr2);
}
//合并结果
print_r(array_merge($arr3 ,$arr1,$arr2));

結果は次のとおりです:

PHP 配列 - マージソートの使用方法?

マージ ソート アルゴリズムは次のとおりです:

1 ) 配列を 2 つの配列に分割します。 。

2) 手順 1 を繰り返して、配列を最小単位に分割します。 。

3) サイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します。このスペースは、マージされたシーケンスを保存するために使用されます。

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

5) 2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインターを次の位置に移動します。

6) ポインタがシーケンスの終わりを超えるまでステップ 3 を繰り返します。 。

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

コードは次のとおりです:

$arr = array(4,7,2,1,5,9,3);
//归并排序函数
function merge_sort($arr){
//递归出口
$len = count($arr);
if($len <= 1) return $arr;
//拆分.
$middle = floor($len / 2);
$left = array_slice($arr,0, $middle);
$right = array_slice($arr, $midd1e);
//假设左边和右边都已经排好序:二路归并
$m = array();
while(count($left) && count($right)){
//只要$arr1和$arr2里面还有元素,就进行循环
//取出每个数组的第一个元素: 进行比较
$arr3[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
}
//返回结果
return array_merge($m, $left ,$right);
}
print_r(merge_sort($arr));

PHP 配列 - マージソートの使用方法?

推奨学習: 「PHP ビデオ チュートリアル

以上がPHP 配列 - マージソートの使用方法?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

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