基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ

青灯夜游
リリース: 2023-04-09 08:42:02
転載
2258 人が閲覧しました


基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ

アルゴリズムはプログラムの中核であると多くの人が言いますが、プログラムの良し悪しを決める鍵は、プログラムの品質です。アルゴリズム。私はジュニア PHPer ですが、アルゴリズムに関することにはほとんど触れていません。ただし、バブル ソート、挿入ソート、選択ソート、クイック ソート、マージ ソートなどの基本的なアルゴリズムを習得する必要があります。

要件: バブル ソート、クイック ソート、選択ソート、挿入ソート、およびマージ ソートを使用して、次の配列内の値を小さい値から大きい値の順に並べ替えます。

$arr=array(11,3,56, 62,21,66,32,78,36,76,39,88,34);

1. バブル ソート

はじめに:

バブル ソートは、単純な並べ替えアルゴリズムです。ソート対象のシーケンスを繰り返し調べて、2 つの要素を順番に比較し、順序が間違っている場合は入れ替えます。配列を訪問する作業は、それ以上の交換が必要なくなるまで繰り返されます。これは、配列がソートされたことを意味します。このアルゴリズムの名前は、小さい要素がスワッピングによって配列の先頭にゆっくりと「浮動」するという事実に由来しています。

ステップ:

1. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。

2. 隣接する要素の各ペアに対して、最初の最初のペアから最後の最後のペアまで同じ作業を実行します。この時点では、最後の要素が最大の数値である必要があります。

3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。

4. 比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

コード:

##
<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ
function bubbleSort($arr) {
    $len = count($arr);
    //该层循环控制 需要冒泡的轮数
    for ($i = 1; $i < $len; $i++) {
        //该层循环用来控制每轮 冒出一个数 需要比较的次数
        for ($k = 0; $k < $len - $i; $k++) {
            if ($arr[$k] > $arr[$k + 1]) {    //从小到大 
                $tmp         = $arr[$k + 1]; // 声明一个临时变量
                $arr[$k + 1] = $arr[$k];
                $arr[$k]     = $tmp;
            }
        }
    }
    return $arr;
}

$arr = bubbleSort($arr);
print_r($arr);
ログイン後にコピー

並べ替え効果:

基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ

2. 選択ソート

はじめに:

選択ソートは、シンプルで直観的な並べ替えアルゴリズムです。仕組みは次のとおりです。まず、ソートされていないシーケンスで最小の要素を見つけて、ソートされたシーケンスの先頭に格納します。次に、引き続きソートされていない残りの要素から最小の要素を見つけて、ソートされたシーケンスの最後に置きます。すべての要素がソートされるまで続きます。

コード:

##

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ
//实现思路 双重循环完成,外层控制轮数,当前的最小值。内层控制比较次数
function selectSort($arr) {

    $len = count($arr);

    //$i 当前最小值的位置, 需要参与比较的元素
    for ($i = 0; $i < $len - 1; $i++) {
        //先假设最小的值的位置
        $p = $i;

        //$j 当前都需要和哪些元素比较,$i 后边的。
        for ($j = $i + 1; $j < $len; $j++) {
            //$arr[$p] 是 当前已知的最小值
            //比较,发现更小的,记录下最小值的位置;并且在下次比较时,应该采用已知的最小值进行比较。
            $p = ($arr[$p] <= $arr[$j]) ? $p : $j;
        }

        //已经确定了当前的最小值的位置,保存到$p中。
        //如果发现 最小值的位置与当前假设的位置$i不同,则位置互换即可
        if ($p != $i) {
            $tmp     = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    //返回最终结果
    return $arr;
}

$arr = selectSort($arr);
print_r($arr);
ログイン後にコピー


基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ3. 挿入ソート

はじめに:

挿入ソートのアルゴリズムの説明は、シンプルで直感的なソート アルゴリズムです。これは、順序付けされたシーケンスを構築することで機能し、並べ替えられていないデータの場合は、並べ替えられたシーケンス内で後ろから前にスキャンし、対応する位置を見つけて挿入します。挿入ソートの実装では、通常、インプレース ソート (つまり、O(1) 個の余分なスペースのみを使用するソート) が使用されるため、後ろから前へのスキャン プロセス中に、繰り返し、徐々にシフトする必要があります。要素を後方にソートし、最新の要素の挿入スペースを提供します。

ステップ:

1. 最初の要素から始めて、要素はソートされたとみなすことができます2. 次の要素を取り出します, ソートされた要素シーケンスを後ろから前にスキャンします。

3. 要素 (ソート済み) が新しい要素より大きい場合は、要素を次の位置に移動します

#4. 手順 3 を繰り返します。並べ替えられた要素が新しい要素

##5 以下になる位置が見つかるまで、新しい要素を位置

##6 に挿入し、手順 2

## を繰り返します。

# コード :

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//插入排序
function insert_sort($arr)
{
    $len=count($arr);
    for($i=1; $i<$len; $i++) {
        //获得当前需要比较的元素值
        $tmp = $arr[$i];
        //内层循环控制 比较 并 插入
        for($j=$i-1; $j>=0; $j--) {
            //$arr[$i];需要插入的元素
            //$arr[$j];需要比较的元素
            if($tmp 
            {
                //发现插入的元素要小,交换位置
                //将后边的元素与前面的元素互换
                $arr[$j+1] = $arr[$j];

                //将前面的数设置为 当前需要交换的数
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
                //由于是已经排序好是数组,则前面的就不需要再次比较了。
                break;
            }
        }
    }
    //将这个元素 插入到已经排序好的序列内。
    //返回
    return $arr;
}

$arr = insert_sort($arr);
print_r($arr);
ログイン後にコピー

4. クイック ソート


導入: ### ###

基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

步骤:

1、从数列中挑出一个元素,称为 “基准”(pivot),

2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码:


<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ
function quick_sort($arr)
{
    //判断参数是否是一个数组
    if(!is_array($arr)) return false;

    //递归出口:数组长度为1,直接返回数组
    $length = count($arr);

    if($length<=1) return $arr;

    //数组元素有多个,则定义两个空数组
    $left = $right = array();

    //使用for循环进行遍历,把第一个元素当做比较的对象
    for($i=1; $i<$length; $i++)
    {
        //判断当前元素的大小
        if($arr[$i] < $arr[0]){  //从小到大 < || 从大到小 >
            $left[]=$arr[$i];
        }else{
            $right[]=$arr[$i];
        }
    }

    //递归调用
    $left=quick_sort($left);
    $right=quick_sort($right);

    //将所有的结果合并
    return array_merge($left,array($arr[0]),$right);
}

$arr = quick_sort($arr);
print_r($arr);
ログイン後にコピー

排序效果:

基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ

5、基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ

利用递归,先拆分、后合并、再排序。

步骤:

  • 均分数列为两个子数列
  • 递归重复上一步骤,直到子数列只有一个元素
  • 父数列合并两个子数列并排序,递归返回数列

代码:


<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];

// 基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ主程序
function mergeSort($arr) {
    $len = count($arr);

    // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组
    if ($len <= 1) {
        return $arr;
    }

    $mid  = intval($len / 2);             // 取数组中间
    $left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left
    $right= array_slice($arr, $mid);          // 拆分数组mid-末尾这部分给右边right
    $left = mergeSort($left);                 // 左边拆分完后开始递归合并往上走
    $right= mergeSort($right);                // 右边拆分完毕开始递归往上走
    $arr  = merge($left, $right);             // 合并两个数组,继续递归

    return $arr;
}

// merge函数将指定的两个有序数组(arrA, arr)合并并且排序
function merge($arrA, $arrB) {
    $arrC = array();
    while (count($arrA) && count($arrB)) {
        // 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值,
        // 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用
        //从小到大 < || 从大到小 >
        $arrC[] = $arrA[0] <p>排序效果:</p><p> </p><p><img src="https://img.php.cn/upload/article/000/000/024/4059d12f5632ac9f990ed52b74747d4b-4.gif" alt="基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージ"    style="max-width:90%"  style="max-width:90%"></p><p>相关推荐:<a href="https://www.php.cn/" target="_blank">PHP教程</a><br></p>
ログイン後にコピー

以上が基本的な PHP アルゴリズムの詳細な説明: バブリング、選択、挿入、高速、マージの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル:
php
ソース:cnblogs.com
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート