QuickSort ir dalīšanas un iekarošanas algoritms. Dalīšanas un iekarošanas algoritmu projektēšanas paradigmā mēs sadalām problēmas apakšproblēmās rekursīvi, pēc tam atrisinām apakšproblēmas un beidzot apvienojam risinājumus, lai atrastu galīgo rezultātu. Šajā rakstā mēs pievērsīsimies QuickSort In
Šajā rakstā tiks apskatīti šādi norādījumi,
Sāksim!
Viena lieta, kas jāpatur prātā, sadalot problēmas apakšproblēmās, ir tā, ka apakšproblēmu struktūra nemainās no sākotnējās problēmas.
Dalīšanas un iekarošanas algoritmam ir trīs darbības:
- Sadaliet: sadaliet problēmu apakšproblēmās
- Iekarot: rekurzīvi atrisināt apakšproblēmas
- Apvienot: apvienojot risinājumus, lai iegūtu gala rezultātu
Ir dažādi algoritmi, kuru pamatā ir dalīšanas un iekarošanas paradigma. Starp tiem ir ātra kārtošana un apvienošana.
Kaut arī vissliktākajā gadījumā QuickSort laika sarežģītība ir O (n2), kas ir vairāk nekā daudzi citi šķirošanas algoritmi, piemēram, Merge Sort un Heap Sort, QuickSort praksē ir ātrāks, jo tā iekšējo cilpu var efektīvi ieviest lielākajā daļā arhitektūru un vairumā reālās pasaules dati.
Parunāsim par Quick sort algoritma ieviešanu. Quicksort algoritmi ņem šarnīra elementu un nodala masīvu ap šarnīra elementu. Quicksot variāciju skaits ir atkarīgs no tā, kā izvēlaties šarnīra elementu. Ir vairāki veidi, kā izvēlēties pagrieziena elementu:
- Pirmā elementa izvēle
- Izvēlieties pēdējo elementu
- Izlases elementa izvēle
- Vidējā elementa izvēle
Nākamā svarīgā lieta, kas jāsaprot, ir partition () funkcija ātrās šķirošanas algoritmā. Sadalīšanās funkcija, lai ņemtu pagrieziena elementu, novietotu to pareizajā pozīcijā, pārvietotu visus elementus, kas ir mazāki par šarnīra elementu, pa kreisi un visus lielākus elementus pa labi. Lai to izdarītu, Quicksort prasa lineāru laiku.
Pēc tam masīvs tiek sadalīts divās daļās no šarnīra elementa (t.i., elementi, kas ir mazāk par šarnīra, un elementi, kas ir lielāki par šarnīru), un abi masīvi tiek rekurzīvi kārtoti, izmantojot Quicksort algoritmu.
Tagad, kad mēs saprotam QuickSort algoritma darbību. Sapratīsim, kā Java ieviest Quicksort algoritmu.
QuickSort Funkcija:
/ * Quicksort funkcijai masīvs ir jāšķiro ar zemāko un augstāko indeksu * /
rekursija fibonacci c ++
void sort (int arr [], int lowIndex, int highIndex) {// Līdz lowIndex = highIndex if (lowIndexTagad apskatīsim sadalīšanas kodu, lai saprastu, kā tas darbojas.
Sadalījums Kods
Sadalīšanas kodā mēs izvēlēsimies pēdējo elementu kā pagrieziena elementu. Mēs šķērsojam visu masīvu (t.i., mūsu gadījumā izmantojot mainīgo j). Mēs sekojam pēdējam mazākajam masīva elementam (t.i., mūsu gadījumā tiek izmantots mainīgais i). Ja atrodam kādu elementu, kas ir mazāks par pagrieziena punktu, mēs pārvietojam pašreizējo elementu a [j] ar arr [i], pretējā gadījumā mēs turpinām šķērsot.
int nodalījums (int arr [], int lowIndex, int highIndex) {// Pēdējā elementa izveidošana kā šarnīrs int pivot = arr [highIndex] // Izmantojot i, lai izsekotu mazākiem elementiem no šarnīra int i = (lowIndex-1) par (int j = lowIndex jTagad, kad esat sapratis Quicksort un partition funkciju, ļaujiet mums ātri apskatīt visu kodu
QuickSort Java kods
klase QuickSort {// Sadalīšanās metode int nodalījums (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) domēnam (int j = lowIndex j// Šķirošanas metode
void sort (int arr [], int lowIndex, int highIndex) {ja (lowIndex// Masīva drukāšanas metode
static void printArray (int arr []) {int n = arr.length par (int i = 0 i// Galvenā metode
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 ('sakārtots masīvs') printArray (arr)}} Izeja:
Tagad pēc iepriekš minētās Java programmas izpildes jūs būtu sapratis, kā darbojas QuickSort un kā to ieviest Java.Tādējādi esam nonākuši pie šī raksta par ‘Quicksort in Java’ beigām. Ja vēlaties uzzināt vairāk,pārbaudiet Autors: uzticams tiešsaistes mācību uzņēmums Edureka. Edureka Java J2EE un SOA apmācības un sertifikācijas kurss ir paredzēts, lai apmācītu jūs gan galvenajiem, gan uzlabotajiem Java jēdzieniem kopā ar dažādiem Java ietvariem, piemēram, Hibernate & Spring.
Vai mums ir jautājums? Lūdzu, pieminējiet to šī emuāra komentāru sadaļā, un mēs sazināsimies ar jums pēc iespējas ātrāk.