ホームページ  >  記事  >  バックエンド開発  >  PHPソートアルゴリズムの原理と概要

PHPソートアルゴリズムの原理と概要

藏色散人
藏色散人転載
2019-10-17 13:30:472467ブラウズ

バブルソートの原理

原理の説明:

隣接する 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ソートアルゴリズムの原理と概要

コード:

    <?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ソートアルゴリズムの原理と概要

<?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ソートアルゴリズムの原理と概要

<?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 サイトの他の関連記事を参照してください。

声明:
この記事はlearnku.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。