Rūšiavimas – tai masyvo elementų išdėstymas taip, kad juos būtų galima išdėstyti didėjančia arba mažėjančia tvarka. Pavyzdžiui, apsvarstykite masyvą A = {A1, A2, A3, A4, ?? An }, masyvas vadinamas didėjančia tvarka, jei A elementai yra išdėstyti taip, kaip A1 > A2 > A3 > A4 > A5 > ? > An .
Apsvarstykite masyvą;
int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )
Masyvas, surūšiuotas didėjančia tvarka, bus pateiktas kaip;
A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }
Yra daug metodų, kuriuos naudojant galima atlikti rūšiavimą. Šioje pamokos dalyje mes išsamiai aptarsime kiekvieną metodą.
Rūšiavimo algoritmai
Rūšiavimo algoritmai aprašyti toliau esančioje lentelėje kartu su aprašymu.
| SN | Rūšiavimo algoritmai | apibūdinimas |
|---|---|---|
| 1 | Burbulų rūšiavimas | Tai paprasčiausias rūšiavimo metodas, kuris atlieka rūšiavimą pakartotinai perkeldamas didžiausią elementą į aukščiausią masyvo indeksą. Tai apima kiekvieno elemento palyginimą su gretimu elementu ir atitinkamai juos pakeičiant. |
| 2 | Rūšiuoti kibiru | Rūšiavimas kibirais taip pat žinomas kaip šiukšlių dėžės rūšiavimas. Jis veikia paskirstydamas elementą į masyvą, dar vadinamą kibirais. Šiuose rūšiavimo algoritmuose segmentai rūšiuojami atskirai, naudojant skirtingą rūšiavimo algoritmą. |
| 3 | Šukų rūšiavimas | „Comb Sort“ yra išplėstinė „Bubble Sort“ forma. Rūšiavimas pagal burbulus lygina visas gretimas reikšmes, o rūšiavimas su šukomis pašalina visas vėžlių reikšmes arba mažas reikšmes sąrašo pabaigoje. |
| 4 | Skaičiavimas Rūšiuoti | Tai rūšiavimo technika, pagrįsta raktais, ty objektai renkami pagal raktus, kurie yra maži sveikieji skaičiai. Skaičiuojantis rūšiavimas apskaičiuoja objektų skaičių ir išsaugo pagrindines jo reikšmes. Naujas masyvas formuojamas pridedant ankstesnius pagrindinius elementus ir priskiriant juos objektams. |
| 5 | Krūvos rūšiavimas | Rūšiuojant krūvą iš masyvo elementų, atsižvelgiant į pasirinkimą, išlaikoma Mini krūva arba maksimali krūva, o elementai rūšiuojami ištrinant šakninį krūvos elementą. |
| 6 | Įterpimo rūšiavimas | Kaip rodo pavadinimas, įterpimo rūšiavimas įterpia kiekvieną masyvo elementą į tinkamą vietą. Tai labai paprastas rūšiavimo būdas, naudojamas kortų kaladės išdėstymui žaidžiant bridžą. |
| 7 | Sujungti Rūšiuoti | Sujungimo rūšiavimas vadovaujasi „skaldyk ir valdyk“ metodu, kai sąrašas pirmiausia padalijamas į lygių elementų rinkinius, o tada kiekviena sąrašo pusė rūšiuojama naudojant sujungimo rūšiavimą. Surūšiuotas sąrašas vėl sujungiamas, kad būtų sudarytas elementarus surūšiuotas masyvas. |
| 8 | Greitas rūšiavimas | Greitasis rūšiavimas yra labiausiai optimizuoti rūšiavimo algoritmai, kurie atlieka rūšiavimą O(n log n) palyginimuose. Kaip ir „Sujungti rūšiavimą“, greitasis rūšiavimas taip pat veikia naudojant „skaldyk ir užkariauk“ metodą. |
| 9 | Rūšiuoti Radix | Radix rūšiavimo atveju rūšiavimas atliekamas taip, kaip mes rūšiuojame pavadinimus pagal abėcėlės tvarką. Tai leninis rūšiavimo algoritmas, naudojamas Inegers. |
| 10 | Pasirinkimas Rūšiuoti | Atrankos rūšiavimas suranda mažiausią masyvo elementą ir įdeda jį į pirmąją sąrašo vietą, tada suranda antrą mažiausią elementą masyve ir įdeda jį į antrąją vietą. Šis procesas tęsiasi tol, kol visi elementai bus perkelti į teisingą tvarką. Jo veikimo laikas O (n2) yra blogiausias nei įterpimo rūšiavimas. |
| vienuolika | Shell Rūšiuoti | Apvalkalo rūšiavimas yra įterpimo rūšiavimo apibendrinimas, kuris pašalina įterpimo rūšiavimo trūkumus, lyginant elementus, atskirtus kelių pozicijų tarpu. |