QuickSort on jagamise ja vallutamise algoritm. Jagamise ja vallutamise algoritmi kujundamise paradigmas jagame alamprobleemides olevad probleemid rekursiivselt, seejärel lahendame alamprobleemid ja lõpuks kombineerime lahendused lõpptulemuse leidmiseks. Selles artiklis keskendume QuickSort In'ile
Järgmisi näpunäiteid käsitletakse selles artiklis,
Alustagem!
Probleemide jagamisel alamprobleemideks tuleb meeles pidada, et alamprobleemide struktuur ei muutu algse probleemi seisuga.
Jaga ja võida algoritmil on 3 sammu:
- Jaga: probleemi jaotamine alamprobleemideks
- Vallutamine: alamprobleemide rekursiivne lahendamine
- Kombineeri: kombineerides lahendused lõpptulemuse saamiseks
Jagamise ja vallutamise paradigmal põhinevaid erinevaid algoritme. Nende hulgas on ka kiire sortimine ja ühendamine.
Kuigi QuickSorti halvim ajaline keerukus on O (n2), mis on rohkem kui paljud teised sorteerimisalgoritmid nagu Sorteerimise ja Hunniku sorteerimine, on QuickSort praktikas kiirem, kuna selle sisemist silmust saab tõhusalt rakendada enamikus arhitektuurides ja enamikus pärismaailma andmed.
Räägime Quick sort algoritmi juurutamisest. Kiirsordi algoritmid võtavad pöördelemendi ja jaotavad massiivi pöördelemendi ümber. Quicksotil on mitmeid variatsioone, mis sõltuvad pöördelemendi valimisest. Pivoti elemendi valimiseks on mitu võimalust:
- Esimese elemendi valimine
- Valige viimane element
- Juhusliku elemendi valimine
- Mediaanelemendi valimine
Järgmine oluline asi, mida mõista, on partitsiooni () funktsioon Kiire sorteerimise algoritmis. Jaotefunktsioon pöördelemendi võtmiseks, asetab selle õigesse asendisse, liigutab kõik pöördelementist väiksemad elemendid vasakule ja kõik elemendid paremale paremale. Quicksortil kulub selleks lineaarne aeg.
Seejärel jagatakse massiiv liigendelemendist kaheks osaks (st elemendid, mis on väiksemad kui pöördetapp, ja elemendid, mis on suuremad kui pöördetapp) ja mõlemad massiivid sorteeritakse rekursiivselt Quicksorti algoritmi abil.
Nüüd, kui oleme aru saanud QuickSorti algoritmi toimimisest. Mõistame, kuidas Quicksorti algoritmi Java-s täiendada.
kuidas jõudu pythonis kasutada
Kiire sortimine Funktsioon:
/ * Quicksorti funktsioon vajab massiivi sorteerimist madalaima ja kõrgeima indeksiga * /
void sort (int arr [], int lowIndex, int highIndex) {// Kuni lowIndex = highIndex if (lowIndexVaatame nüüd jaotuskoodi, et mõista, kuidas see töötab.
Jaotus Kood
Jaotuskoodis valime pöördelemendiks viimase elemendi. Me läbime kogu massiivi (st kasutame meie puhul muutujat j). Jälgime massiivi viimast väikseimat elementi (st kasutame meie puhul muutujat i). Kui leiame mõne pöördepunktist väiksema elemendi, liigutame praeguse elemendi a [j] arr [i] -ga, muidu jätkame liikumist.
int partitsioon (int arr [], int lowIndex, int highIndex) {// Viimase elemendi tegemine pöördetapina int pivot = arr [highIndex] // i abil pivoti väiksemate elementide jälgimine int i = (lowIndex-1) jaoks (int j = lowIndex jNüüd, kui olete aru saanud funktsioonist Quicksort & partition, vaadake kiiret koodi
Kiire sortimine Java kood
klass QuickSort {// Sektsioonimeetod int partitsioon (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j// Sorteerimismeetod
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Massiivi printimise meetod
staatiline tühine printArray (int arr []) {int n = arr.length for (int i = 0 i// Peamine meetod
public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('sorteeritud massiiv') printArray (arr)}} Väljund:
Nüüd pärast ülaltoodud Java-programmi käivitamist oleksite aru saanud, kuidas QuickSort töötab ja kuidas seda Java-s rakendada.Nii oleme jõudnud selle artikli juurde, mis käsitleb teemat ‘Quicksort in Java’. Kui soovite rohkem teada saada,vaadake autor Edureka, usaldusväärne veebipõhine õppefirma. Edureka Java J2EE ja SOA koolitus- ja sertifitseerimiskursus on mõeldud selleks, et õpetada teid nii Java põhiliste kui ka edasijõudnute kontseptsioonide jaoks koos erinevate Java-raamistikega nagu Hibernate & Spring.
Kas teil on meile küsimus? Palun mainige seda selle blogi kommentaaride jaotises ja võtame teiega ühendust niipea kui võimalik.