Vergleich der Sortieralgorithmen

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Beim Sortieren werden Daten nach bestimmten Standards geordnet. Zusätzlich zur aufsteigenden numerischen Reihenfolge können Sie mehrere Kriterien wie Zustand, Name oder Erstellungszeitpunkt verwenden.

Auswahl sortieren

Suchen Sie im verbleibenden Abschnitt den kleinsten Wert und ersetzen Sie ihn durch den vorherigen.

for (int i = 0; i < Count - 1; ++i)
{
    int MinIndex = i;

    for (int j = i + 1; j < Count; ++j)
    {
        if (Values[j] < Values[MinIndex])
        {
            MinIndex = j;
        }
    }

    std::swap(Values[i], Values[MinIndex]);
}

Einfach zu implementieren, aber die Anzahl der Vergleiche ist großO(N²)Daher ist es nicht für große Datenmengen geeignet.

Sortierung zusammenführen

Teilen Sie das Array in zwei Hälften, sortieren Sie jedes und führen Sie es dann zusammen. Zeitkomplexität istO(N log N)Es kann als stabile Sortierung implementiert werden, für die Zusammenführung ist jedoch temporärer Speicher erforderlich.

schnelle Sortierung

Teilen Sie kleine und große Werte basierend auf dem Pivot auf und ordnen Sie jeden Abschnitt neu an. Der Durchschnitt istO(N log N)Wenn die Pivot-Auswahl jedoch weiterhin schlecht ist,O(N²)Sie können nach unten gehen

Anstatt die Ausrichtung selbst im tatsächlichen C++-Code neu zu erstellen,std::sortUndstd::stable_sortZuerst verwenden.

std::sort(Units.begin(), Units.end(),
    [](const Unit& A, const Unit& B)
    {
        return A.Speed > B.Speed;
    });

Die direkte Implementierung des Algorithmus durch dessen Untersuchung und die Verwendung einer verifizierten Standardbibliothek im Produktcode haben unterschiedliche Zwecke.