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

この記事では、PHP でクイックソートを実装するための 3 つの方法を主に紹介します。3 つの方法にはそれぞれ長所と短所があります。必要な方は参考にしてください。

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

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

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

関数 Quick_sort($array) {

if(count($array) $key = $array[0];

$rightArray = array();

$leftArray = array();

for($i = 1; $i if($array[$i] >= $key) {

$rightArray[] = $array[$i];

} 他 {

$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) 時間がかかります)

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

関数 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) などの極端なケースを考慮すると、段階的に理解できます。

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

関数 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)

そうです--;

$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/740818.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/740818.html技術記事この記事では主に、PHP でクイック ソートを実装する 3 つの方法を紹介します。それぞれに利点と欠点があります。必要な場合は、次の 3 つの PHP クイック ソートの例を参照してください。最初の方法は非効率的ですが、最も効果的です。