Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge

Viele Leute sagen, dass der Algorithmus der Kern des Programms ist. Der Schlüssel dafür, ob ein Programm besser oder schlechter ist, ist die Qualität des Algorithmus . Als Junior-PHPer habe ich allerdings wenig Erfahrung mit algorithmischen Dingen. Sie müssen jedoch noch grundlegende Algorithmen wie Blasensortierung, Einfügungssortierung, Auswahlsortierung, Schnellsortierung und Zusammenführungssortierung beherrschen.

Anforderungen: Verwenden Sie Blasensortierung, Schnellsortierung, Auswahlsortierung, Einfügungssortierung und Zusammenführungssortierung, um die Werte im Array unten von klein nach groß zu sortieren.

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

1. Blasensortierung

Einführung :

Bubble Sort ist ein einfacher Sortieralgorithmus. Es durchläuft wiederholt die zu sortierende Sequenz, vergleicht nacheinander die beiden Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Der Besuch des Arrays wird wiederholt, bis kein Austausch mehr erforderlich ist, was bedeutet, dass das Array sortiert wurde. Der Name dieses Algorithmus rührt von der Tatsache her, dass kleinere Elemente durch den Austausch langsam an die Spitze des Arrays „schweben“.

Schritte:

1. Vergleichen Sie benachbarte Elemente. Wenn das erste größer als das zweite ist, tauschen Sie beide aus.

2. Machen Sie die gleiche Arbeit für jedes Paar benachbarter Elemente, vom ersten Paar am Anfang bis zum letzten Paar am Ende. Zu diesem Zeitpunkt sollte das letzte Element die größte Zahl sein.

3. Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.

4. Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen vorhanden sind.

Code:

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge
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);

Sortiereffekt:

2. Auswahlsortierung

Einführung:

Auswahlsortierung ist ein einfacher und intuitiver Sortieralgorithmus. So funktioniert es. Suchen Sie zunächst das kleinste Element in der unsortierten Sequenz und speichern Sie es am Anfang der sortierten Sequenz. Suchen Sie dann weiterhin das kleinste Element aus den verbleibenden unsortierten Elementen und fügen Sie es dann am Ende der sortierten Sequenz ein. Und so weiter, bis alle Elemente sortiert sind.

Code:

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge
//实现思路 双重循环完成，外层控制轮数，当前的最小值。内层控制比较次数
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);

3 🎜>

Einführung:

Die Algorithmusbeschreibung von Insertion Sort ist ein einfacher und intuitiver Sortieralgorithmus. Es funktioniert, indem es eine geordnete Sequenz erstellt. Bei unsortierten Daten wird die sortierte Sequenz von hinten nach vorne durchsucht, um die entsprechende Position zu finden und einzufügen. Bei der Implementierung der Einfügungssortierung wird normalerweise die In-Place-Sortierung verwendet (d. h. eine Sortierung, die nur O(1) zusätzlichen Platz beansprucht). Daher müssen die sortierten Elemente während des Scanvorgangs von hinten nach vorne wiederholt und schrittweise sortiert werden nach hinten verschoben, um Platz zum Einfügen des neuesten Elements zu schaffen.

Schritte:

1. Beginnend mit dem ersten Element kann davon ausgegangen werden, dass das Element sortiert wurde

2 , in Scannen Sie die sortierte Elementsequenz von hinten nach vorne

3 Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position

4 , Bis die Position gefunden wird, an der das sortierte Element kleiner oder gleich dem neuen Element ist

5. Fügen Sie das neue Element an der Position ein

6. Wiederholen Sie Schritt 2

Code:

<?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. Schnelle Sortierung

Einleitung:

Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge通常明显比其他Ο(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];
//Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge
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);

排序效果：

5、Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge

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

步骤:

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

代码：

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

// Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge主程序
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="Ausführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge"    style="max-width:90%"  style="max-width:90%"></p><p>相关推荐：<a href="https://www.php.cn/" target="_blank">PHP教程</a><br></p>

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung der grundlegenden PHP-Algorithmen: Bubbling, Selection, Insertion, Fast, Merge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!