QuickSort je algoritem deli in osvoji. V paradigmi načrtovanja algoritma Divide & Conquer probleme razdelimo na podprobleme rekurzivno, nato rešimo podprobleme in na koncu združimo rešitve, da poiščemo končni rezultat. V tem članku se bomo osredotočili na QuickSort In
V tem članku bodo zajeti naslednji napotki:
Začnimo!
Pri razdeljevanju problemov na podprobleme je treba upoštevati, da se struktura podproblemov od prvotnega problema ne spremeni.
Algoritem Divide & Conquer ima tri korake:
- Divide: Razčlenitev problema na podprobleme
- Conquer: Rekurzivno reševanje podproblemov
- Kombiniraj: kombiniranje rešitev za doseganje končnega rezultata
Obstajajo različni algoritmi, ki temeljijo na paradigmi deli in vladaj. Med njimi so hitro razvrščanje in združevanje.
Čeprav je najslabša časovna zapletenost QuickSort O (n2), kar je več kot mnogi drugi algoritmi za razvrščanje, kot sta Merge Sort in Heap Sort, je QuickSort v praksi hitrejši, saj je njegovo notranjo zanko mogoče učinkovito uporabiti na večini arhitektur podatki iz resničnega sveta.
Pogovorimo se o izvajanju algoritma za hitro razvrščanje. Algoritmi Quicksort zavzamejo vrtilni element in razdelijo matriko okoli vrtilnega elementa. Obstaja več različic Quicksota, ki so odvisne od tega, kako izberete vrtilni element. Vrtilni element lahko izberemo na več načinov:
- Izbiranje prvega elementa
- Izberite zadnji element
- Izbiranje naključnega elementa
- Srednja izbira elementa
Naslednja pomembna stvar, ki jo je treba razumeti, je funkcija particije () v algoritmu za hitro razvrščanje. Funkcija particije za prevzem vrtilnega elementa, ga postavi v desni položaj, premakne vse elemente, manjše od vrtilnega elementa, na levo in vse elemente večje na desno. Quicksort za to potrebuje linearni čas.
Nato je polje iz vrtilnega elementa razdeljeno na dva dela (tj. Elementi, ki so manjši od vrtišča in elementi večji od vrtišča), oba polja pa se rekurzivno razvrstijo z algoritmom Quicksort.
java plača razvijalcev v Indiji
Zdaj, ko razumemo delovanje algoritma QuickSort. Razumejmo, kako uporabiti algoritem Quicksort v Javi.
QuickSort Funkcija:
/ * Funkcija Quicksort zahteva, da je polje razvrščeno z najnižjim in najvišjim indeksom * /
void sort (int arr [], int lowIndex, int highIndex) {// Do lowIndex = highIndex if (lowIndexZdaj pa si oglejmo particijsko kodo, da bomo razumeli, kako deluje.
Pregrada Koda
V particijski kodi bomo zadnji element izbrali kot vrtilni element. Prehodimo celotno matriko (tj. V našem primeru uporabimo spremenljivko j). Spremljamo zadnji najmanjši element v matriki (tj. V našem primeru uporabljamo spremenljivko i). Če najdemo kateri koli element, ki je manjši od vrtišča, trenutni element a [j] zamenjamo z arr [i], sicer nadaljujemo s prehodom.
int particija (int arr [], int lowIndex, int highIndex) {// Izdelava zadnjega elementa kot pivot int pivot = arr [highIndex] // Uporaba i za sledenje manjših elementov iz pivot int i = (lowIndex-1) for (int j = lowIndex jZdaj, ko ste razumeli funkcijo Quicksort & partition, nam na hitro oglejte celotno kodo
QuickSort Java koda
class QuickSort {// Metoda particije int particija (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) za (int j = lowIndex j// Metoda razvrščanja
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Metoda za tiskanje polja
static void printArray (int arr []) {int n = dolžina arr za (int i = 0 i// Glavna metoda
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 ('razvrščeno polje') printArray (arr)}} Izhod:
Zdaj po izvedbi zgornjega programa Java bi razumeli, kako QuickSort deluje in kako ga implementirati v Javo.Tako smo prišli do konca tega članka o 'Quicksort v Javi'. Če želite izvedeti več,preverite Edureka, zaupanja vredno podjetje za spletno učenje. Edurekin tečaj za usposabljanje in certificiranje Java J2EE in SOA je zasnovan tako, da vas usposobi za temeljne in napredne koncepte Java, skupaj z različnimi Java okviri, kot sta 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.