PHPで簡単にソートする3つの方法-PHPチュートリアル-php.cn

PHPで簡単にソートする3つの方法

WBOY

リリース： 2016-07-25 08:53:52

オリジナル

1070 人が閲覧しました

function Quick_sort($array) {
if(count($array) <= 1) return $array;
$key = $array[0];
$rightArray = array( );
$leftArray = array();
for($i = 1; $i < count($array); $i++) {
if($array[$i] >= $key) {
$ 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 メソッドと呼ばれています (詳細は、興味があれば、goole で入手できます。説明) 最も古典的な一方向トラバーサルを使用して、中央値を見つけます。ただし、このアルゴリズムは最悪の場合 O(n*n) です (たとえば、同じ値を持つ配列には n-1 回の除算が必要で、各除算で要素を削除するには O(n) 時間がかかります)。コード：

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] < $key に変更されると、 $array[$left] に変更されます。 <= $key は最悪です状況が O(n*n) に悪化するだけでなく、各比較の消費に加えて、n 回の対話による追加のオーバーヘッドも発生します。この問題には、丸暗記する生徒向けのテストポイントが他に 2 つあります。 1. 真ん中の 2 つの while は交換可能ですか?もちろん、高速ディスクでは左側の初期値を保存するために余分なスペースが必要になるため、入れ替えることはできません。このように、左右を入れ替えると、右側が最初に保存された値を上書きするために使用されます。は中央値の左辺値です。それ以外の場合は問題が発生します。この文を参照してください $array[$left] = $array[$right]; 2. $array[$right] = $key; この文の意味は省略可能です。この文は省略できません。2 つの値の順序 (5,2) などの極端なケースを考慮すると、段階的に理解できます。コード： < $key改成$array[$left] <= $key则最坏情况不但会堕落为O(n*n).而且除了每次比较的消耗外，还会产生n次交互的额外开销。该题还有另外两个考点，针对死记硬背的同学： 1，中间的两个while可否互换。当然不能互换，因为对于快盘需要一个额外的空间保存初始的左值，这样左右互换的时候，先用右边覆盖已经保存为中值的左值，否则会出现问题。见这句$array[$left] = $array[$right]; 2，$array[$right] = $key; 该语句含义可否省略。该句不能省略，大家可以考虑一个极端情况比如两个值的排序（5,2），逐步看下就明白了。代码：