Array-Sortier- und Suchalgorithmus in PHP

PHP ist eine sehr beliebte Programmiersprache, die verschiedene Datentypen und Algorithmen unterstützt, von denen Array-Sortierung und Suchalgorithmen grundlegende und wichtige Bestandteile sind. In diesem Artikel werden häufig verwendete Array-Sortier- und Suchalgorithmen in PHP sowie deren Anwendungsszenarien und Effizienzanalysen vorgestellt.

1. Array-Sortierung

PHP bietet eine Vielzahl von Array-Sortiermethoden, einschließlich Blasensortierung, Einfügungssortierung, Auswahlsortierung, Schnellsortierung, Zusammenführungssortierung usw. Das Folgende ist eine Einführung und ein Beispielcode für mehrere häufig verwendete Algorithmen:

1. Bubble Sort

Bubble Sort ist ein einfacher, aber ineffizienter Sortieralgorithmus. Seine Grundidee besteht darin, mit der ersten Ordnung des Arrays zu beginnen , werden die Größen benachbarter Elemente nacheinander verglichen. Wenn das linke Element größer als das rechte Element ist, werden ihre Positionen vertauscht. Nach dieser Vergleichsrunde wird das größte Element an das Ende des Arrays verschoben. Beginnen Sie dann mit dem ersten Element und wiederholen Sie den obigen Vorgang. Die zeitliche Komplexität beträgt O (n ^ 2).

Beispielcode:

function bubble_sort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

2. Einfügungssortierung

Einfügungssortierung ist ein relativ einfacher Sortieralgorithmus. Seine Grundidee besteht darin, zu sortierende Daten in eine bereits geordnete Reihenfolge einzufügen, um den Sortierzweck zu erreichen. Unter der Annahme, dass die vorherigen Elemente sortiert wurden, beginnen Sie mit dem zweiten Element des Arrays und suchen Sie nach einer geeigneten Position für den Einfügevorgang. Ähnlich wie bei der Blasensortierung beträgt auch die zeitliche Komplexität O(n^2).

Beispielcode:

function insertion_sort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $temp = $arr[$i];
        for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$j + 1] = $temp;
    }
    return $arr;
}

3. Quick Sort

Quick Sort ist ein häufig verwendeter und effizienter Sortieralgorithmus. Seine Grundidee besteht darin, ein beliebiges Element im Array als Basiswert auszuwählen und die verbleibenden Elemente dann in zwei zu unterteilen Teilsequenzen: Die Zahlen auf der linken Seite sind alle kleiner als der Basiswert und die Zahlen auf der rechten Seite sind alle größer als der Basiswert. Wiederholen Sie dann die obigen Schritte für die linke und rechte Teilsequenz, bis die Länge der Teilsequenz 1 oder 0 beträgt. Die Zeitkomplexität der schnellen Sortierung beträgt O(n log2 n) und es handelt sich um eine instabile Sortierung.

Beispielcode:

function quick_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $pivot_key = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] <= $pivot_key) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($pivot_key), $right_arr);
}

2. Array-Suche

Array-Suchalgorithmen in PHP umfassen hauptsächlich lineare Suche, binäre Suche und Hash-Suche. Das Folgende ist eine Einführung und ein Beispielcode für mehrere häufig verwendete Algorithmen:

1. Lineare Suche

Die Grundidee besteht darin, mit dem ersten Element des Arrays zu beginnen Geben Sie nacheinander die Schlüsselwörter der Elemente ein, um festzustellen, ob sie identisch sind. Geben Sie den Index des Elements zurück, andernfalls geben Sie -1 zurück. Die zeitliche Komplexität der linearen Suche beträgt O(n).

Beispielcode:

function linear_search($arr, $key) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        if ($arr[$i] == $key) {
            return $i;
        }
    }
    return -1;
}

2. Binäre Suche

Die Grundidee besteht darin, das geordnete Array in zwei Teile zu unterteilen und jeweils die Größe der mittleren Elemente und Schlüsselwörter zu vergleichen sind gleich Geben Sie dann den Index des Elements zurück, andernfalls wird der Suchbereich entsprechend der Größenbeziehung um die Hälfte reduziert, bis das Zielelement gefunden wird. Die zeitliche Komplexität der binären Suche beträgt O(log2 n).

Beispielcode:

function binary_search($arr, $key) {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($arr[$mid] == $key) {
            return $mid;
        } elseif ($arr[$mid] > $key) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

3. Hash-Suche

Hash-Suche ist ein effizienter Suchalgorithmus, der Hash-Tabellen verwendet. Die Grundidee besteht darin, den Schlüssel jedes Elements einer Hash-Tabelle zuzuordnen, seine Position mithilfe einer Hash-Funktion zu berechnen und dann das erforderliche Element an dieser Position zu finden. Die zeitliche Komplexität der Hash-Suche beträgt O(1), es muss jedoch eine Hash-Tabelle erstellt und verwaltet werden.

Das Obige ist eine Einführung und ein Beispielcode für Array-Sortier- und Suchalgorithmen, die häufig in PHP verwendet werden. Die Auswahl verschiedener Algorithmen entsprechend den tatsächlichen Anwendungsszenarien und der Datengröße kann die Effizienz des Codes verbessern.

Das obige ist der detaillierte Inhalt vonArray-Sortier- und Suchalgorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!