Ai auzit vreodată despre termenul „Împarte și cucerește”? Acest articol se bazează destul de specific pe această abordare. Merge Sort este un algoritm „împărțiți și cuceriți” în care împărțim mai întâi problema în subprobleme și apoi le îmbinăm pentru a ne cuceri soluția. Iată o imagine de ansamblu completă a conceptului de sortare fuzionată în J .
- Ce este sortarea merge în Java?
- Funcționare de tip fuzionat
- Exemplu: Diagrama
- Implementare
- Complexitate
Ce este sortarea merge în Java?
Sortarea Merge este una dintre cele mai populare algoritmi de sortare disponibil și urmează o abordare de divizare și cucerire. O problemă este împărțită în subprobleme și combinată împreună pentru a ajunge la soluția finală!
Acum, ce se întâmplă exact în timpul funcționării sortării fuziunii? Să înțelegem în detaliu.
Funcționare de tip fuzionat
Există doi pași urmați de sortarea de îmbinare în timpul procesului:
- Divide: În acest pas, matricea de intrare este împărțită în 2 jumătăți, pivotul este punctul de mijloc al matricei. Acest pas se efectuează recursiv pentru toate jumătățile de matrice până când nu mai există jumătăți de matrice de divizat în continuare.
- A cuceri: În acest pas, sortăm și îmbinăm matricile împărțite de jos în sus și ajungem la matricea sortată.
Această abordare vă ajută să sortați mai ușor subpărțile problemelor mai întâi și, prin urmare, să ajungeți la soluție.
Permiteți-mi să vă arăt o reprezentare picturală a tipului de îmbinare.
Exemplu: Diagrama
Aici, ați văzut cum arată o sortare de îmbinare. Principalul concept de sortare fuzionată este că este nevoie de mai puțin timp pentru sortare. Acum, trecem la partea noastră de implementare!
Implementare
pachet MyPackage public class MergeSort {void merge (int arr [], int beg, int mid, int end) {int l = mid - beg + 1 int r = end - mid int LeftArray [] = new int [l] int RightArray [] = new int [r] for (int i = 0 iIeșire:
Matricea sortată
unu
4
17
22
2. 3
40
Patru cinci
51
55
90Așa arată un cod Java care descrie sortarea fuzionării. Trecând la următorul segment.
Complexitate
Complexitatea este bifurcată în două tipuri: complexitatea timpului și complexitatea spațiului. În cazul sortării prin îmbinare, datele sunt așa cum se arată mai jos:
Complexitate Cel mai bun caz
setați java classpath windows 10Caz mediu
Cel mai rău caz
Complexitatea timpului
O (n jurnal n)
O (n jurnal n)
O (n jurnal n)
Complexitatea spațială
-
-
Pe)
Cu aceasta, voi încheia acest articol. Sper că conținutul explicat mai sus a adăugat o valoare adăugată cunoștințelor dvs. Java. Vom continua să explorăm lumea Java împreună. Rămâneți aproape!
Verificați de Edureka, o companie de învățare online de încredere, cu o rețea de peste 250.000 de elevi mulțumiți răspândiți pe tot globul. Cursul de formare și certificare Java J2EE și SOA al Edureka este conceput pentru studenți și profesioniști care doresc să fie dezvoltator Java. Cursul este conceput pentru a vă oferi un început important în programarea Java și pentru a vă instrui atât pentru conceptele Java de bază, cât și pentru cele avansate, împreună cu diverse cadre Java, cum ar fi Hibernate & Spring
Ai o întrebare pentru noi? Vă rugăm să o menționați în secțiunea de comentarii a acestui „ Merge sort in Java ”Pe blog și vă vom răspunde cât mai curând posibil.