So sortieren Sie in der C++ Standard Template Library (STL)

Verwenden Sie die Funktion sort() aus <algorithm> der C++-Standardbibliothek, um ein Array oder einen Vektor an Ort und Stelle zu ordnen. Standardmäßig sortiert sie den halboffenen Bereich von first bis zu, aber nicht einschließlich, last in aufsteigender Reihenfolge. Übergeben Sie einen Komparator, um eine andere Reihenfolge zu wählen.

Die Funktion sort() verwenden, um ein Array oder einen Vektor in C++ zu sortieren

std::sort akzeptiert Random-Access-Iteratoren, daher funktioniert es mit Arrays und Vektoren. Es kann std::set oder std::map nicht an Ort und Stelle neu ordnen, weil diese Container keine Random-Access-Iteratoren bereitstellen. Dieses vollständige Programm sortiert sowohl ein Array als auch einen Vektor:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin und std::end stellen den Bereich des Arrays bereit, während der Vektor seine Iteratoren begin() und end() verwendet. Dieses Programm wird als nicht ausgeführtes Beispiel bereitgestellt; seine Ausgabe wird weggelassen, bis sie in der konfigurierten Laufzeitumgebung beobachtet wird. Beide Aufrufe verändern die ursprünglichen Elemente, sodass späterer Code sie in der neuen Reihenfolge sieht. Um nur einen Teil eines Containers zu sortieren, übergeben Sie Iteratoren, die diesen Abschnitt begrenzen.

Ein Array oder einen Vektor in C++ in absteigender Reihenfolge sortieren

Übergeben Sie std::greater<> als drittes Argument, um Werte vom größten zum kleinsten zu ordnen. Binden Sie <functional> für den Komparator ein. Zum Beispiel sortiert std::sort(values.begin(), values.end(), std::greater<>{}); einen Vektor in absteigender Reihenfolge. Der Komparator ändert die Ordnungsregel, ohne zu ändern, welcher Bereich sortiert wird.

partial_sort() verwenden, um einen Teil eines Arrays oder Vektors zu sortieren

Verwenden Sie partial_sort(first, middle, last), wenn nur ein Präfix geordnet sein muss. Es platziert die kleinsten middle - first Elemente in sortierter Reihenfolge vor middle. Für die Elemente von middle bis last ist keine bestimmte Reihenfolge garantiert. Zum Beispiel wählt std::partial_sort(values.begin(), values.begin() + 3, values.end()); die drei kleinsten Werte für die ersten drei Positionen aus.

Einen benutzerdefinierten Komparator mit sort() in C++ verwenden

Ein Komparator ermöglicht es Ihnen, Werte nach einem Schlüssel wie der Stringlänge zu ordnen. Zum Beispiel platziert std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); kürzere Strings zuerst. Ein Komparator muss eine strikte schwache Ordnung definieren: Er muss konsistent sein und darf ein Element nicht als vor sich selbst stehend betrachten. Strings mit gleicher Länge sind unter diesem Vergleich äquivalent, daher ist ihre relative Reihenfolge nicht spezifiziert. Binden Sie bei Verwendung dieses Beispiels <string> zusammen mit <algorithm> ein.

Mit is_sorted() prüfen, ob ein Bereich sortiert ist

std::is_sorted(first, last) gibt true zurück, wenn der Bereich von first bis zu, aber nicht einschließlich, last gemäß dem Standardvergleich geordnet ist, und andernfalls false. Es prüft den Bereich, ohne seine Elemente neu anzuordnen. Geben Sie denselben Komparator an, der für eine benutzerdefinierte Reihenfolge verwendet wurde, wenn Sie diese Reihenfolge prüfen, wie in std::is_sorted(words.begin(), words.end(), compare).

Zeitkomplexität von Sortieralgorithmen

Für std::sort spezifiziert der Standard im schlimmsten Fall O(N log N) Vergleiche, wobei N die Anzahl der Elemente im Bereich ist. Dies beschreibt, wie der Aufwand mit der Bereichslänge wächst; es verspricht keine bestimmte Sortierimplementierung. std::partial_sort verwendet ungefähr N log K Vergleiche, wenn K Elemente aus N ausgewählt und geordnet werden, während std::is_sorted höchstens N - 1 Vergleiche durchführt. Diese Grenzen helfen zu unterscheiden, ob ein Bereich vollständig sortiert, nur ein Präfix geordnet oder eine bestehende Reihenfolge geprüft wird.