Järjestäminen ja osittaminen: sort, stable_partition
Järjestä ja osita kontteja std::sort- ja std::stable_partition-algoritmeilla.
Järjestäminen ja osittaminen: sort, stable_partition on ilmainen C++ Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu C++ Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. C++ Academy-kurssilla on yhteensä 4 oppituntia.
std::sort
Yleiskäyttöinen lajittelualgoritmi. Keskimääräinen aikavaativuus on O(N log N). Toimii paikallaan. Vakaata järjestystä ei taata.
#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascendingMukautettu vertailija
Välitä vertailija (lambda tai funktori), jos haluat lajitella muiden kriteerien perusteella.
std::sort(v.begin(), v.end(),
[](int a, int b) { return a > b; }); // descendingMukautettujen tyyppien lajittelu
Anna vertailija, joka vertailee tiettyjä jäseniä, tai määritä tyypille operator<.
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
Kuten sort, mutta säilyttää samanarvoisten alkioiden keskinäisen järjestyksen. Hieman hitaampi (tyypillisesti O(N log^2 N) lisämuistia).
std::partial_sort
Sijoittaa pienimmät k alkiota alkuun lajiteltuina. Jäljelle jäävien alkioiden järjestystä ei määritellä. Nopeampi kuin koko alueen lajittelu, kun tarvitset vain kärkijoukon.
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, sortedstd::nth_element
Jakaa alueen niin, että nth-kohdassa oleva alkio olisi samassa kohdassa kuin täysin lajitellulla alueella. Kaikki sitä edeltävät alkiot ovat ≤ kyseistä alkiota ja kaikki sen jälkeiset ≥ sitä. Keskimääräinen aikavaativuus on O(N).
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest elementstd::is_sorted
Tarkistaa, onko alue jo lajiteltu.
if (std::is_sorted(v.begin(), v.end())) {
std::cout << "already sorted";
}std::partition
Järjestää alueen uudelleen niin, että predikaatin täyttävät alkiot tulevat ensin. Palauttaa iteraattorin ensimmäiseen predikaattia täyttämättömään alkioon. Ei säilytä keskinäistä järjestystä.
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 oddstd::stable_partition
Kuten partition, mutta säilyttää ryhmien sisäisten alkioiden keskinäisen järjestyksen.
Lajittelu usean avaimen perusteella
Käytä vertailijaa, joka vertailee ensin ensisijaista avainta ja sen ollessa samaa toissijaista avainta.
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äärihaku lajitelluista alueista
Kun alue on lajiteltu, käytä std::lower_bound-, std::upper_bound- ja std::binary_search-algoritmeja O(log N) -aikaisiin hakuihin.
Pikatarkistus
Mikä algoritmi säilyttää samanarvoisten alkioiden keskinäisen järjestyksen lajittelun jälkeen?
Kertaus
Käytä yleiseen lajitteluun std::sort-algoritmia, kun samanarvoisten alkioiden järjestyksellä on merkitystä std::stable_sort-algoritmia, kärkijoukon valintaan std::partial_sort-algoritmia, valintaan std::nth_element-algoritmia ja ryhmittelyyn std::partition- tai std::stable_partition-algoritmia.
Opi C++ tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 51
- Oppitunnit
- 203
Usein kysytyt kysymykset
Onko oppitunti ”Järjestäminen ja osittaminen: sort, stable_partition” ilmainen?
Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa C++ Academy-oppimispolun 3 oppituntia, myös oppitunnin “Järjestäminen ja osittaminen: sort, stable_partition”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. C++ Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Järjestäminen ja osittaminen: sort, stable_partition”?
Järjestä ja osita kontteja std::sort- ja std::stable_partition-algoritmeilla. Harjoittelet C++ Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni C++ Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin C++ Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Järjestäminen ja osittaminen: sort, stable_partition”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä C++ Academy-oppitunnilla?
Kyllä. Jokainen C++ Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Muuttamattomat algoritmit: find, count, all_of
- Muokkaavat algoritmit: transform, copy_if, replace
- Järjestäminen ja osittaminen: sort, stable_partition
- Numeeriset algoritmit: accumulate, reduce, transform_reduce