PHP_PHP チュートリアルでクイック ソートを実装する 3 つの方法を共有する

3 つの PHP クイック ランキングの例を書きました。1 つ目は非効率ですが、最も単純で理解しやすいものです。2 つ目は、アルゴリズムの紹介で提供されている一方向のトラバース方法です。 -way トラバーサルを使用して中央値を見つけます。 3 つのグループのアルゴリズムの実装と比較は次のとおりです:

方法 1: この方法はより直観的ですが、多くのスペースが失われ、効率の低いマージ関数が使用されます。 3 つの方法の中で最も効率が低くなります。最悪の場合、アルゴリズムは (O(n*n)) に縮退します

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

function Quick_sort($array) {
if(count($array) $key = $array[0] ;
$ rightArray = array();
$leftArray = array();
for($i = 1; $i ) {
$rightArray[] = $array [$i];
} else {
$leftArray[] = $array[$i];
}
}
$leftArray = Quick_sort($leftArray);
$rightArray = Quick_sort($rightArray);
return array_merge( $leftArray、array($key)、$rightArray);
}

方法 2: このアルゴリズムは、「アルゴリズム入門」に由来し、Nico Lomuto メソッドと呼ばれています (詳細については、興味がある場合は Google で参照してください)。これは、最も古典的な一方向トラバーサルを使用して中央値を見つけます。
しかし、このアルゴリズムは最悪の場合 O(n*n) です (たとえば、同じ値を持つ配列には n-1 回の除算が必要で、各除算では要素を削除するのに O(n) 時間がかかります)

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

function Quick_sort(&$array, $start, $end) {
if ($start >= $end) return;
$mid = $start;
for ( $ i = $start + 1; $i if ($array[$i] < $array[$mid]) {
$mid++;
$tmp = $array[ $ i];
$array[$i] = $array[$mid];
$array[$mid] = $tmp;
}
}
$tmp = $array[$start];
$array[$ start ] = $array[$mid];
$array[$mid] = $tmp;
Quick_sort($array, $start, $mid - 1);
Quick_sort($array, $mid + 1, $end) ;
}

方法 3: この方法は、基本的には一般的な教科書の書き方です。まず、左から右に移動して、中央の要素よりも小さい要素をスキップします。同時に、右から左に移動して、中央の要素よりも大きい要素をスキップします。真ん中のそれから

交差がない場合は、両側の値を交換し、中間点が見つかるまでループを続けます。このメソッドは同じ要素を処理するときに依然としてスワップするため、最悪の場合は O(nlogn) になることに注意してください

効率。ただし、次の関数で $array[$right] > $key が $array[$right] >=$key または $array[$left] < に変更されると、 $left ] <= $key は最悪です

状況は O(n*n) に悪化するだけでなく、n 回のインタラクションによる追加のオーバーヘッドも生成されます。この質問には、暗記する生徒向けに、他に 2 つのテスト ポイントがあります:

1: 真ん中の 2 つの while は交換可能ですか。もちろん、高速ディスクは左側の初期値を保存するために余分なスペースを必要とするため、入れ替えることはできません。このように、左右を入れ替える場合は、最初に右側を使用して保存された値を上書きする必要があります。

は中央値の左辺値です。それ以外の場合は問題が発生します。この文を参照 $array[$left] = $array[$right];

2: $array[$right] = $key; このステートメントの意味は省略できます。この文は省略できません。2 つの値の順序 (5,2) などの極端なケースを考慮すると、段階的に理解できます。

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

function Quick_sort_swap(&$array, $start, $end) {

if($end <= $start) return;
$key = $array [$start ];
$left = $start;
$right = $end;
while($left < $right) {
while($left < $right && $array[$right] > $key )
$ right--;
$array[$left] = $array[$right];
while($left < $right && $array[$left] < $key)
$left++;
$array [$right ] = $array[$left];
}
$array[$right] = $key;
Quick_sort_swap(&$array, $start, $right - 1);
Quick_sort_swap(&$array, $right +1, $end);
}

http://www.bkjia.com/PHPjc/740664.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/740664.html技術記事 PHP のクイック ランキングの例を 3 つ書きました。最初の例は非効率ですが、最も単純で理解しやすいものです。2 番目の例は、アルゴリズムの紹介で提供されている一方向のトラバーサルです。中央値を見つけるためのウェイトラバーサル...