Einführung in Bubbling-, binäre Einfügungs- und Schnellsortierungsalgorithmen-PHP-Tutorial-php.cn

Einführung in Bubbling-, binäre Einfügungs- und Schnellsortierungsalgorithmen

jacklove

Freigeben： 2023-03-31 12:28:01

Original

2228 Leute haben es durchsucht

1. Blasensortierungsalgorithmus
Prozess:
1 Durchlaufen Sie das gesamte Array und vergleichen Sie jedes Paar benachbarter Elemente, z. B. $ a[. $i]>$a[$i+1] tauscht Positionen und jeder Vergleich eliminiert eine umgekehrte Reihenfolge.
2. Nach jedem Zyklus wird die Anzahl der beim nächsten Mal erforderlichen Zyklen um 1 reduziert.

<?php
// 冒泡排序
$arr = createarr(20);
printarr($arr);
popsort($arr);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function popsort(&$arr){
    for($i=0,$length=count($arr)-1; $i<$length; $i++){
        for($j=0; $j<$length-$i; $j++){
            if($arr[$j]>$arr[$j+1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }    
}
?>

Nach dem Login kopieren

2. Binäre Einfügungssortierung

Prozess:
Zuerst Insgesamt ist das ursprüngliche Array eine geordnete Sequenz, $low=0 $high=count($arr)-1.
2. Vergleichen Sie die einzufügende Zahl mit dem Element in der Mitte des Arrays.
Wenn es größer als das mittlere Element ist, wird $low=$mid+1 als Anfang des Arrays verwendet das nächste Urteil.
Wenn es kleiner als das mittlere Element ist, wird $high=$mid-1 als Ende des Arrays für die nächste Beurteilung verwendet.
3. Bis $low>$high endet, ist $low die Position, an der das neue Element eingefügt wird.
4. Verschieben Sie alle Elemente beginnend bei $low im Array um eins nach hinten und fügen Sie dann neue Elemente an der $low-Position ein.

<?php
// 二分法插入排序
$arr = createarr(20);
$key = mt_rand(0,99);
printarr($arr);
echo &#39;key=&#39;.$key.&#39;<br>&#39;;
binsort($arr, $key);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,99));
    }
    sort($arr); // 有序序列
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function binsort(&$arr, $key){
    $low = 0;
    $high = count($arr)-1;
    while($low<=$high){
        $m = $low + (int)(($high-$low)/2);
        $mkey = $arr[$m];
        if($key>=$mkey){
            $low = $m + 1;
        }else{
            $high = $m - 1;
        }
    }
    // 移动插入位置之后的元素,插入新元素
    for($i=count($arr)-1; $i>=$low; $i--){
        $arr[$i+1] = $arr[$i];
    }
    $arr[$low] = $key;
}
?>

Nach dem Login kopieren

3. Schneller Sortiervorgang
1. Suchen Sie im Allgemeinen ein Element im Array take Das erste Element des Arrays wird als Schlüssel 2 verwendet. i=0, j=Array-Länge-1
3. j] Positionen tauschen
4. i++ Wenn arr[i]>key, arr[i] und arr[j] die Positionen tauschen
5.
6. Führen Sie 1, 2, 3, 4, 5 (rekursiv) auf den linken und rechten Elementsätzen aus, getrennt durch Schlüssel.

<?php
// 快速排序
$arr = createarr(20);
printarr($arr);
quicksort($arr, 0, count($arr)-1);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function quicksort(&$arr, $low, $high){
    if($low>=$high){
        return ;
    }
    $key = $arr[$low];
    $i = $low;
    $j = $high;
    $flag = 1;
    while($i!=$j){
        switch($flag){
            case 0:
                if($arr[$i]>$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 1;
                }else{
                    $i++;
                }
                break;
            case 1:
                if($arr[$j]<$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 0;
                }else{
                    $j--;
                }
                break;
        }
    }
    quicksort($arr, $low, $i-1);
    quicksort($arr, $i+1, $high);
}
?>

Nach dem Login kopieren

In diesem Artikel werden Blasenbildung, Dichotomie-Einfügung und schneller Sortieralgorithmus erläutert. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website.

Verwandte Empfehlungen:

So filtern Sie HTML-Tag-Attributklassen über PHP

So verwenden Sie PHP, um sensible Zeichenfolgenbezogene Vorgänge zu ersetzen

Über PHP, das Ordner und Dateiklassen durchläuft und Klassen verarbeitet

Das obige ist der detaillierte Inhalt vonEinführung in Bubbling-, binäre Einfügungs- und Schnellsortierungsalgorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!