PricingLoginStart free
C++ Academy · Lektion

Sortering och partitionering: sort, stable_partition

Sortera och partitionera containers med std::sort och std::stable_partition

Lektion 3 av 413 steg

Sortering och partitionering: sort, stable_partition är en gratis lektion i C++ Academy på CoddyKit. Detta är lektion 3 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för C++ Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i C++ Academy innehåller totalt 4 lektioner.

std::sort

Den vanligaste sorteringsalgoritmen. O(N log N) i genomsnitt. På plats. Stabilitet garanteras inte.

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

Anpassad komparator

Skicka med en komparator (lambda eller funktor) för att sortera efter andra kriterier.

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

Sortering av anpassade typer

Ange en komparator som jämför specifika medlemmar, eller definiera operator< för 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

Som sort, men bevarar den relativa ordningen mellan likvärdiga element. Något långsammare (vanligen O(N log^2 N) extra minne).

std::partial_sort

Placerar de minsta k elementen först, sorterade. De återstående elementen har en ospecificerad ordning. Snabbare än fullständig sortering när endast de k främsta behövs.

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

Delar upp intervallet så att elementet på positionen nth är det som skulle finnas där i ett fullständigt sorterat intervall. Alla element före det är ≤ det på nth-positionen, och alla efter är ≥ det. O(N) i genomsnitt.

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

std::is_sorted

Kontrollerar om ett intervall redan är sorterat.

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

std::partition

Ordnar om ett intervall så att element som uppfyller ett predikat kommer först. Returnerar iteratorn till det första elementet som inte uppfyller predikatet. Inte 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 bevarar den relativa ordningen inom varje grupp.

Sortering efter flera nycklar

Använd en komparator som jämför den primära nyckeln och därefter den sekundära om den primära är lika.

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ärsökning i sorterade intervall

När intervallet är sorterat kan std::lower_bound, std::upper_bound och std::binary_search användas för uppslag på O(log N).

Snabbtest

Vilken algoritm bevarar den relativa ordningen mellan likvärdiga element efter sortering?

Besvara frågan i den interaktiva lektionen

Sammanfattning

Använd std::sort för generell sortering, std::stable_sort när ordningen mellan likvärdiga element spelar roll, std::partial_sort för de k främsta elementen, std::nth_element för urval och std::partition/std::stable_partition för gruppering.

Gratis att börja

Lär dig C++ med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser
51
Lektioner
203
Börja lära dig gratisVisa hela kursen

Vanliga frågor

Är lektionen ”Sortering och partitionering: sort, stable_partition” gratis?

Ja – du kan läsa vilka 3 lektioner som helst i lärvägen C++ Academy, inklusive ”Sortering och partitionering: sort, stable_partition”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i C++ Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Sortering och partitionering: sort, stable_partition”?

Sortera och partitionera containers med std::sort och std::stable_partition Ni övar på C++ Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig C++ Academy?

Du behöver inga förkunskaper. Utbildningen i C++ Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.

Hur lång tid tar lektionen ”Sortering och partitionering: sort, stable_partition”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här C++ Academy-lektionen?

Ja. Varje C++ Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

  1. Icke-modifierande algoritmer: find, count, all_of
  2. Modifierande algoritmer: transform, copy_if, replace
  3. Sortering och partitionering: sort, stable_partition
  4. Numeriska algoritmer: accumulate, reduce, transform_reduce
← Tillbaka till C++ Academy