PricingLoginStart free
C++ Academy · Lektion

Sortering og partitionering: sort, stable_partition

Sortér og partitionér containere med std::sort og std::stable_partition

Lektion 3 af 413 trin

Sortering og partitionering: sort, stable_partition er en gratis C++ Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i C++ Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C++ Academy-kurset indeholder 4 lektioner i alt.

std::sort

Den centrale sorteringsalgoritme. O(N log N) i gennemsnit. Udføres på stedet. Stabilitet er ikke garanteret.

#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending

Tilpasset sammenligning

Send en sammenligningsfunktion (lambda eller funktor) for at sortere efter andre kriterier.

std::sort(v.begin(), v.end(),
    [](int a, int b) { return a > b; });   // descending

Sortering af brugerdefinerede typer

Angiv en sammenligningsfunktion, der sammenligner bestemte medlemmer, eller definér operator< for typen.

struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });

std::stable_sort

Samme som sort, men bevarer den indbyrdes rækkefølge for ens elementer. Lidt langsommere (typisk O(N log^2 N) ekstra hukommelse).

std::partial_sort

Placér de k mindste elementer først (sorteret). De resterende elementer står i en uspecificeret rækkefølge. Hurtigere end en fuld sortering, når du kun har brug for de bedste k elementer.

std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sorted

std::nth_element

Opdel området, så elementet på positionen nth er det samme, som det ville være i et fuldt sorteret område. Alt før er ≤ nth, og alt efter er ≥. O(N) i gennemsnit.

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest element

std::is_sorted

Kontrollér, om et område allerede er sorteret.

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "already sorted";
}

std::partition

Omarrangér et område, så elementer, der opfylder et prædikat, kommer først. Returnerer iteratoren til det første element, der ikke opfylder prædikatet. Ikke stabil.

std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });
// even numbers come first, then odd

std::stable_partition

Som partition, men bevarer den indbyrdes rækkefølge inden for hver gruppe.

Sortering efter flere nøgler

Brug en sammenligningsfunktion, der sammenligner den primære nøgle og derefter den sekundære, hvis den primære er ens.

std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    });

Binær søgning i sorterede områder

Når området er sorteret, kan du bruge std::lower_bound, std::upper_bound og std::binary_search til opslag i O(log N).

Hurtigt tjek

Hvilken algoritme bevarer den indbyrdes rækkefølge for ens elementer efter sortering?

Besvar den i den interaktive lektion

Opsummering

Brug std::sort til generel sortering, std::stable_sort, når rækkefølgen for ens elementer er vigtig, std::partial_sort til de bedste k elementer, std::nth_element til udvælgelse og std::partition/std::stable_partition til gruppering.

Gratis at komme i gang

Lær C++ med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser
51
Lektioner
203
Start gratisSe hele kurset

Ofte stillede spørgsmål

Er lektionen “Sortering og partitionering: sort, stable_partition” gratis?

Ja — alle 3 lektioner i læringssporet C++ Academy, inklusive “Sortering og partitionering: sort, stable_partition”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. C++ Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Sortering og partitionering: sort, stable_partition”?

Sortér og partitionér containere med std::sort og std::stable_partition Du øver dig i C++ Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på C++ Academy?

Der kræves ingen tidligere erfaring. C++ Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.

Hvor lang tid tager lektionen “Sortering og partitionering: sort, stable_partition”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne C++ Academy-lektion?

Ja. Alle C++ Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

  1. Algoritmer uden ændring: find, count, all_of
  2. Ændring: transform, copy_if, replace
  3. Sortering og partitionering: sort, stable_partition
  4. Numeriske algoritmer: accumulate, reduce, transform_reduce
← Tilbage til C++ Academy