PHPクイックソートアルゴリズムの詳細説明、ソートアルゴリズムの詳細説明_PHPチュートリアル

PHPクイックソートアルゴリズムの詳細説明、ソートアルゴリズムの詳細説明

コンセプト

これは百度百科事典から借りた非常に鮮やかな写真です:

クイックソートアルゴリズムはバブルアルゴリズムを最適化したものです。彼のアイデアは、まず配列を分割し、大きな要素の値を一時的な配列に置き、小さな要素の値を別の一時的な配列に入れることです (分割点は配列内の任意の要素値にすることができます。通常は最初の値を使用します)要素、つまり $array[0]) を作成し、これら 2 つの一時配列の上記の分割を繰り返し、最後に小さい配列要素と大きい配列要素をマージします。ここでは再帰の考え方が使われています。

PHPの実装

コードをコピーします コードは次のとおりです:

/*
クイックソート
*/

関数クイックソート($array)
{
If(!isset($array[1]))
$array を返す;
$mid = $array[0] // 分割用のキーワードを取得します (通常は最初の要素) $leftArray = 配列(); $rightArray = array();

foreach($array as $v)

{

If($v > $mid)
$rightArray[] = $v // $mid より大きい数値を配列に入れます
; if($v $leftArray[] = $v // $mid より小さい数値を別の配列に代入します
; }

$leftArray = QuickSort($leftArray) // 小さい配列を再度分割します

$leftArray[] = $mid // 分割した要素を小さな配列の末尾に追加します。忘れずに

;
$rightArray = QuickSort($rightArray) // 大きい配列を再度分割します

Return array_merge($leftArray,$rightArray); // 2 つの結果を結合します

}

バブルアルゴリズムとの比較

ここでは、以前に書いたバブル アルゴリズムによって実装された並べ替えを比較しました。このアルゴリズムはバブル アルゴリズムよりもはるかに効率的であることがわかります。

コードをコピーします コードは次のとおりです:

$a = array_rand(range(1,3000), 1500); //バブルアルゴリズムが1600要素を超えるとメモリ不足のメッセージが出ますが、ここでは両者の差を計測するために次のように設定します。 1500。バブル アルゴリズムを確実に完了できます。

shuffle($a); //シャッフルされた配列を取得します
$t1 = マイクロタイム(true);
QuickSort($a); //クイックソート
$t2 = マイクロタイム(true);
echo (($t2-$t1)*1000).'ms&​​lt;br/>';

require('./maopao.php'); //ここで引用されているのは、以前に書いたバブルアルゴリズムのソートです $t1 = マイクロタイム(true);

マオパオ($a); //バブル
$t2 = マイクロタイム(true);
echo (($t2-$t1)*1000).'ms';

実行結果:

コードをコピーします コードは次のとおりです:

12.10880279541ミリ秒

772.64094352722ミリ秒

http://www.bkjia.com/PHPjc/909348.html

www.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/909348.html技術記事 PHP クイック ソート アルゴリズムの詳細な説明 ソート アルゴリズムの概念の詳細な説明は、Baidu Encyclopedia の図から借用しました。クイック ソート アルゴリズムは、バブル アルゴリズムを最適化したものです。彼の想いは…