Razvrščanje je ena najbolj osnovnih in uporabnih funkcij, ki se uporablja za podatke. Njegov namen je urediti podatke na določen način, ki se lahko povečuje ali zmanjšuje v skladu z zahtevami. V C ++ STL je vgrajena funkcija z imenom 'sort ()', ki nam omogoča enostavno izvajanje algoritma za razvrščanje. V tem članku bomo raziskovali funkcijo razvrščanja v jeziku C ++,
V tem članku bodo zajeti naslednji napotki:
- Funkcija razvrščanja ()
- Primer - razvrščanje podatkov v naraščajočem vrstnem redu
- Primer - razvrščanje podatkov v padajočem vrstnem redu
- Delno_razvrsti
Nadaljujemo s tem člankom o funkciji razvrščanja v jeziku C ++
Razvrsti ( )
To je vgrajena funkcija datoteke glave algoritma, ki se uporablja za razvrščanje vsebnikov kot polja, vektorjev v določenem vrstnem redu. Interno je ta funkcija izvedena kot hitro razvrščanje
Quicksort je algoritem deli in osvoji. Quicksort najprej razdeli velik seznam elementov na dva manjša podseznama: spodnje elemente in višje elemente. Quicksort nato rekurzivno razvrsti pod-sezname.
Koraki so naslednji:
1. Na seznamu izberite naključni element (običajno zadnji element), imenovan vrtišče.
2. Seznam prerazporedite tako, da bodo vsi elementi z vrednostmi, manjšimi od vrtišča, pred vrtiščem, medtem ko bodo vsi elementi z vrednostmi, večjimi od vrtišča, prišli za njim, enake vrednosti pa se lahko tako ali drugače imenujejo postopek particije.
3. Rekurzivno razvrstite pod-seznam manjših elementov in pod-seznam večjih elementov, znova izberite vrtišče na pod-seznamu in jih razdelite.
Osnovni primer rekurzije so seznami velikosti nič ali ena, ki jih ni treba nikoli razvrščati in tako z njihovim združevanjem razvrstimo svoj seznam.
Quicksort je v praksi hitrejši od drugih algoritmov O (n log n), kot je razvrščanje po vstavitvi ali razvrščanje po mehurčkih. Quicksort je mogoče implementirati z algoritmom particioniranja na mestu, kar pomeni, da je mogoče celotno razvrščanje opraviti le z dodatnim prostorom O (log n). Quicksort ni stabilna sorta.
Njegova zapletenost je naslednja:
Najboljši primer - O (n log n)
Najslabši primer - O (n ^ 2)
Povprečni primer - O (n log n)
Sintaksa:
razvrsti (prva, zadnja)
Tukaj,
prvi - je indeks (kazalec) prvega elementa v obsegu, ki ga je treba razvrstiti.
zadnji - je indeks (kazalec) zadnjega elementa v obsegu, ki ga je treba razvrstiti.
Na primer, želimo razvrstiti elemente polja ‘arr’ od 1 do 10 položaja, uporabili bomo razvrščanje (arr, arr + 10) in bo razvrstilo 10 elementov v naraščajočem vrstnem redu.
Vrnjena vrednost
Nobenega
Kompleksnost
kaj je metoda javascript
Povprečje zapletenosti razvrščanja je N * log2 (N), kjer je N = zadnji - prvi.
Podatkovno območje
Predmeti v obsegu [prvi, zadnji) so spremenjeni.
Izjeme
Preobremenitve s parametrom predloge, ki je imenovan kot napake poročila ExecutionPolicy, kot sledi:
Če algoritmu ne uspe dodeliti pomnilnika, se std :: bad_alloc vrne kot izjema.
Če izvajanje funkcije, ki se prikliče kot del algoritma, vrže izjemo std :: terminate.
Nadaljujemo s tem člankom o funkciji razvrščanja v jeziku C ++
Primer - razvrščanje podatkov v naraščajočem vrstnem redu:
#include z uporabo imenskega prostora std int main () {matrika [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (array) / sizeof (array [0] ) // 'sizeof' poda velikost celotnega polja, tj. velikost vsakega znaka * št. znakov // tako da dobimo št. znakov // sizeof (matriko) delimo z velikostjo katerega koli znaka matrice // tukaj je matrika [0] sort (array, array + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Izhod:
Pojasnilo
Iz zgornjega primera vidimo, da funkcija sort () privzeto sortira matriko v naraščajočem vrstnem redu.
Nadaljujemo s tem člankom o funkciji razvrščanja v jeziku C ++
Primer - razvrščanje podatkov v padajočem vrstnem redu:
Za razvrščanje podatkov polja v padajočem vrstnem redu moramo uvesti tretji parameter, ki se uporablja za določanje vrstnega reda razvrščanja elementov. Za razvrščanje podatkov v padajočem vrstnem redu lahko uporabimo funkcijo “larger ()”.
#include using namespace std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (array) / sizeof (array [0] ) sort (array, array + n, larger ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Izhod:
Exp l anacija
Tu funkcija sort () opravi primerjavo na način, ki postavi večji element pred.
Nadaljujemo s tem člankom o funkciji razvrščanja v jeziku C ++
Delno_razvrsti
C ++ STL nam ponuja funkcijo delnega razvrščanja, funkcija je podobna funkciji sort (), vendar se za razliko od funkcije sort () ne uporablja za razvrščanje celotnega obsega, temveč za razvrščanje le njegovega dela. Elemente razvrsti v obsegu [prvi, zadnji) tako, da se elementi pred srednjim elementom razvrstijo v naraščajočem vrstnem redu, medtem ko elementi za sredino ostanejo, kot je.
Z njim lahko poiščemo največji element, če za razvrščanje prvega mesta uporabimo funkcijski objekt
c ++ fibonaccijev rekurziven
Primer
#include #include #include z uporabo imenskega prostora std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr delno_sort (vec.begin (), vec.begin () + 1, vec.end (), večji ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } Izhod:
Pojasnilo:
Zgornjo kodo lahko uporabimo za iskanje največjega števila v nizu, za iskanje najmanjšega števila v seriji pač moramo odstraniti večji ukaz.
Tako smo prišli do konca tega članka o funkciji razvrščanja v jeziku C ++. Če želite izvedeti več, si oglejte Java Training by Edureka, zaupanja vredno podjetje za spletno učenje. Edureka tečaji so zasnovani tako, da vas usposobijo za osnovne in napredne koncepte Java, skupaj z različnimi Java okviri, kot so Hibernate & Spring
Imate vprašanje za nas? Prosimo, omenite to v oddelku za komentarje tega spletnega dnevnika, mi pa se vam bomo javili v najkrajšem možnem času.