ホームページ >バックエンド開発 >PHPチュートリアル >PHPソートアルゴリズムの原理と概要
バブルソートの原理
原理の説明:
隣接する 2 つの要素を一度に比較し、大きい要素が後方に移動し、小さい要素が前方に移動します (場所を交換します)。最大の要素が見つかるまで。泡と同じように、大きなものは下に沈み、小さなものは上に上がります。
プロセス:
順序のない配列 $arr = [8, 9, 3, 6, 1, 4]
第一次外循环 :找出最大值 9,要俩俩相比,比 5 次。 8 9 3 6 1 4 第一次, 8 跟 9 比,9 大,所以没有交换位置。 8 3 9 6 1 4 第二次, 9 跟 3 比, 9 大,交换位置。 8 3 6 9 1 4 第三次, 9 跟 6 比, 9 大,交换位置。 8 3 6 1 9 4 第四次, 9 跟 1 比, 9 大,交换位置。 8 3 6 1 4 9 第五次, 9 跟 4 比, 9 大,交换位置。 第二次外循环:找出第二大值 8,要俩俩相比,比 4 次。因为上一步已经找到最大值了。 3 8 6 1 4 9 第一次,8 跟 3 比,8 大, 交换位置。 3 6 8 1 4 9 第二次,8 跟 6 比,8 大, 交换位置。 3 6 1 8 4 9 第三次,8 跟 1 比,8 大, 交换位置。 3 6 1 4 8 9 第四次,8 跟 4 比,8 大, 交换位置。 第三次外循环:找出第三大的值 6,要俩俩相比,比三次。 3 6 1 4 8 9 第一次,3 跟 6 比,6 大,位置没有变化。 3 1 6 4 8 9 第二次,6 跟 1 比,6 大,交换位置。 3 1 4 6 8 9 第三次,6 跟 4 比,6 大,交换位置。 第四次外循环:找出第四大的值 4,要俩俩相比,比 2 次。 1 3 4 6 8 9 第一次, 3 跟 1 比, 3 大,交换位置。 1 3 4 6 8 9 第二次, 3 跟 4 比, 4 大,位置不变。 第五次外循环:找出第五大的值 3, 比一次就够了。 1 3 4 6 8 9 比一次。1 跟 3 比,3 大,位置没有变化。
概要:
1. 外側のループには要素数 - 1 回が必要です。最大値を見つける責任があります。
2. 内側のループは層ごとに減少します。 2 つを比較し、要素の位置を交換します。
コード:
<?php function bubbleSort($arr) { $len = count($arr);//获取元素个数 for ($i = 0; $i < $len - 1; $i ++) {//找出最大值 $flag = 0;//做一个标记 for($j = 0; $j < $len - 1 - $i; $j++) {//俩俩相比较,交换位置 if ($arr[$j] > $arr[$j + 1]) { //$temp = $arr[$j];//存当前元素 //$arr[$j] = $arr[$j + 1];//把当前元素的值换成下一个元素的值 //$arr[$j + 1] = $temp;//把下一个元素的值换成上一个元素的值。 list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];//来自lovecn的评论,有时候思维有些固化。 $flag = 1;//交换位置就记录。 } } if ($flag == 0) {//没有发生交换位置,说明排序已经完成。可以推出循环。 break; } } return $arr; }
クイックソート原則 (再帰的)
原則の説明:
From array最初の値を参照オブジェクトとして取り、この値より小さい値を左側に配置し、この値より大きい値を右側に配置します。これにより、2 つの新しい配列が作成され、2 つの配列を再帰的に処理してから、参照左側がオブジェクト、右側がマージです。注: 再帰がある場合は、再帰出口を見つける必要があります。そうしないと、再帰が継続します。
プロセス:
プロセスを言葉で説明するのは面倒なので、インターネットで画像を見つけました。プロセスは非常に明確です。
コード:
<?php function quickSort($arr) { $len = count($arr); //递归出口 if($len <= 1) { return $arr; } $markValue = $arr[0];//参照物。 $left = $right = [];//定义左边和右边。 for($i = 1; $i < $len; $i++) {//从1开始循环,因为第一个元素当作参照物。 if($arr[$i] > $markValue) {//大于参照物的放在右边。 $right[] = $arr[$i]; } else {//小于和等于参照物的元素都放进左边,这样会避免如果数组有重复元素时,会漏掉元素。 $left[] = $arr[$i]; } } return array_merge(quickSort($left), [$markValue], quickSort($right)); }
挿入ソート
原則の説明:
ソートされます配列は 2 つの部分に分割され、配列の最初の要素は順序付きセットに配置され、残りの要素は順序なしセットに配置されます。並べ替える必要がある数値と、以前に並べ替えたデータを後ろから前に比較して、その数値以下の数値が見つかるまで、その数値を対応する位置に挿入します。
私の記憶法:
2 つのボックスがあるとします。最初のボックスは透明で空で、順序付けされた要素を含めるために使用されます。2 番目のボックスは不透明で空です。完全で、順序付けされていない要素が含まれています。要素。 (実際には、何でも好きなふりをしてかまいません。覚えやすいものがベストです)。
1. ステップ 1: 不透明なボックスから要素を取り出し、透明なボックスに直接投入します。
2. ステップ 2: 不透明なボックスから要素を取り出し、それを前に置きます透明なボックスと比較してください。大きい場合は後ろに、小さい場合は前に置きます。
3. 2 番目のステップを繰り返しますが、正しい位置が見つかるまで透明ボックス内の要素が増えるため、毎回実行する必要がある比較の数が増加します。
プロセス:
<?php function insertSort($arr) { $len = count($arr); if ($len <= 1) {//一个元素或者没有元素,排序无意义。 return $arr; } for($i = 0; $i < $len - 1; $i++) { for($j = $i + 1; $j > 0; $j--){//每次比较次数增加。因为有序集合元素在增加。 if ($arr[$j] < $arr[$j - 1]) { list($arr[$j], $arr[$j - 1]) = [$arr[$j - 1], $arr[$j]];//交换位置。 } } } return $arr; }
選択の並べ替え
原則の説明:
1 回a time 配列から最小要素または最大要素を削除し、指定された位置に配置します。
ステップ 1: 最初の要素に Holy Fire Order を与え、それを後続の各要素と比較します (最小の要素を採用します)。それより小さい要素に遭遇した場合は、最小の要素に聖火トークンを与える方法がわかるまで、それに聖火トークンを与えてください。
ステップ 2: 位置を交換し、ホーリー ファイア オーダーを 2 番目の兄弟エレメントに渡し、最初のステップを繰り返します。
プロセス:
<?php function selectSort($arr) { $len = count($arr); if ($len <= 1) {//一个元素或者没有元素,排序没有意义。 return $arr; } for($i = 0; $i < $len - 1; $i++) { $p = $i;//给第一个元素圣火令。 for($j = $i + 1; $j < $len; $j++) { if ($arr[$j] < $arr[$p]) {//有圣火令的元素和后面的元素比较,把圣火令交给较小的元素。 $p = $j; } } list($arr[$p], $arr[$i]) = [$arr[$i], $arr[p]]; } return $arr; }
以上がPHPソートアルゴリズムの原理と概要の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。