QuickSort je algoritmus rozdelenia a dobývania. V paradigme návrhu algoritmu Divide & Conquer rozdelíme problémy na čiastkové problémy rekurzívne, potom čiastkové problémy vyriešime a nakoniec ich spojíme a nájdeme konečný výsledok. V tomto článku sa zameriame na QuickSort In
typy množín v Jave
V tomto článku sa budeme zaoberať nasledujúcimi ukazovateľmi,
Poďme začať!
Pri delení problémov na čiastkové problémy je treba mať na pamäti, že štruktúra čiastkových problémov sa oproti pôvodnému problému nemení.
Algoritmus Divide & Conquer má 3 kroky:
- Rozdeliť: Rozdelenie problému na čiastkové problémy
- Dobyť: Rekurzívne riešenie podproblémov
- Kombinujte: Kombináciou riešení získate konečný výsledok
Existujú rôzne algoritmy založené na paradigme rozdelenia a dobývania. Medzi nimi je aj rýchle triedenie a zlúčenie.
Aj keď najhoršia časová zložitosť QuickSortu je O (n2), čo je viac ako mnoho iných algoritmov triedenia ako Merge Sort a Heap Sort, QuickSort je v praxi rýchlejší, pretože jeho vnútornú slučku je možné efektívne implementovať na väčšine architektúr a vo väčšine údaje zo skutočného sveta.
Poďme si povedať o implementácii algoritmu rýchleho triedenia. Algoritmy Quicksort preberajú otočný prvok a rozdeľujú pole okolo prvku otočného prvku. Existuje množstvo variácií produktu Quicksot, ktoré závisia od toho, ako vyberiete otočný prvok. Existuje niekoľko spôsobov, ako zvoliť otočný prvok:
- Vyberá sa prvý prvok
- Vyberte posledný prvok
- Vyberanie náhodného prvku
- Vyberá sa stredný prvok
Ďalšou dôležitou vecou, ktorú treba pochopiť, je funkcia partition () v algoritme rýchleho triedenia. Funkcia oddielu, ktorá prevezme otočný prvok, umiestni ho do správnej polohy, presunie všetky prvky menšie ako otočný prvok doľava a všetky prvky väčšie doprava. Quicksort to trvá lineárne.
Potom je pole rozdelené na dve časti od otočného prvku (t. J. Prvky menšie ako otočné a prvky väčšie ako otočné) a obe polia sú rekurzívne zoradené pomocou algoritmu Quicksort.
Teraz, keď už rozumieme fungovaniu algoritmu QuickSort. Poďme pochopiť, ako implementovať algoritmus Quicksort v Jave.
úlohy a zodpovednosti vývojára hadoop
QuickSort Funkcia:
/ * Funkcia Quicksort vyžaduje, aby bolo pole zoradené podľa najnižšieho a najvyššieho indexu * /
void sort (int arr [], int lowIndex, int highIndex) {// until lowIndex = highIndex if (lowIndexTeraz sa pozrime na kód oddielu, aby sme pochopili, ako to funguje.
Priečka Zákonníka
V kóde rozdelenia vyberieme posledný prvok ako otočný prvok. Prejdeme celé pole (t. J. V našom prípade použijeme premennú j). Sledujeme posledný najmenší prvok v poli (t. J. V našom prípade používame premennú i). Ak nájdeme akýkoľvek prvok menší ako otočný čap, presunieme aktuálny prvok a [j] s arr [i], inak pokračujeme v traverze.
int oddiel (int arr [], int lowIndex, int highIndex) {// Vytvorenie posledného prvku ako pivot int pivot = arr [highIndex] // Použitie i na sledovanie menších prvkov z pivot int i = (lowIndex-1) pre (int j = lowIndex jTeraz, keď ste pochopili funkciu Quicksort a funkciu oddielov, poďme sa rýchlo pozrieť na celý kód
QuickSort Java kód
class QuickSort {// Partition Method int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j// Metóda triedenia
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Metóda tlače poľa
static void printArray (int arr []) {int n = arr.length for (int i = 0 i// Hlavná metóda
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 ('triedené pole') printArray (arr)}} Výkon:
Teraz po vykonaní vyššie uvedeného programu Java by ste pochopili, ako funguje program QuickSort a ako ho implementovať v prostredí Java.Tak sme sa dostali na koniec tohto článku o „Quicksort v Jave“. Ak sa chcete dozvedieť viac,pozrite sa na Edureka, dôveryhodná online vzdelávacia spoločnosť. Výcvikový a certifikačný kurz Edureka Java J2EE a SOA je navrhnutý tak, aby vás vyškolil pre základné aj pokročilé koncepty Java spolu s rôznymi rámcami Java, ako je Hibernate & Spring.
Máte na nás otázku? Uveďte to prosím v sekcii komentárov tohto blogu a my sa vám ozveme čo najskôr.