PHP-Lernimplementierung der Einfügungssortierung

Der Hauptinhalt dieses Artikels ist die Verwendung von PHP zur Implementierung der Einfügungssortierung. Es ist eine einfache, aber klassische Algorithmusfrage. Ich frage mich, ob Sie sich daran erinnern.

Grundidee der Einfügungssortierung : Teilen Sie das Array in zwei Bereiche (sortierter Bereich und unsortierter Bereich). Nehmen Sie an, dass sich das erste Element des Arrays im sortierten Bereich befindet erstes Element Alle folgenden Elemente befinden sich im unsortierten Abschnitt. Beim Sortieren wird eine doppelschichtige Schleife verwendet, um die zu sortierenden Elemente aus dem unsortierten Teil herauszunehmen und den unsortierten Teil schrittweise zu reduzieren. Die innere Schleife wird verwendet, um die Einfügeposition aus dem sortierten Teil zu ermitteln ist, kontinuierlich aus dem sortierten Teil. Suchen Sie nach Elementen, die größer als die zu sortierenden Elemente sind, und verschieben Sie dann die Elemente des größeren sortierten Bereichs nach hinten. Das Endergebnis der Rückwärtsbewegung ist, dass das letzte Element den sortierten Bereich einnimmt die ursprüngliche Position des zu sortierenden Elements und die Mitte des sortierten Bereichs ist eine leere Position) und fügt schließlich das zu sortierende Element in den leeren Raum ein, der nach dem Verschieben des Elements übrig bleibt.

//插入排序
function insert_sort($arr) {
    //获取数组单元个数
    $count = count($arr);
    //外层循环用于从未排序区域中取出待排序元素
    for ($i=1; $i < $count; $i++) {
        //获取当前需要插入已排序区域的元素值
        $temp = $arr[$i];
        //内层循环用于从已排序区域寻找待排序元素的插入位置
        for ($j=$i-1; $j >= 0; $j--) {
            //如果$arr[$i]比已排序区域的$arr[$j]小，就后移$arr[$j]
            if ($temp < $arr[$j]) {        
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $temp;
            } else {
                //如果$arr[$i]不小于$arr[$j]，则对已排序区无需再排序
                break;
            }
        }
    }
    return $arr;
}

$arr = array(6, 19, 26, 62, 88, 99, 18, 16, 1);
var_dump(insert_sort($arr));
　　测试结果：

　

Verwandte Tutorials: PHP-Video-Tutorial

Das obige ist der detaillierte Inhalt vonPHP-Lernimplementierung der Einfügungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!