QuickSort este un algoritm de divizare și cucerire. În paradigma de proiectare a algoritmului Divide & Conquer, împărțim recursiv problemele din subprobleme, apoi rezolvăm subproblemele și combinăm în cele din urmă soluțiile pentru a găsi rezultatul final. În acest articol ne vom concentra pe QuickSort In
Următoarele indicații vor fi tratate în acest articol,
Sa incepem!
final în final și finalizează în java
Un lucru pe care trebuie să-l țineți cont de faptul că împărțiți problemele în subprobleme este că structura subproblemelor nu se schimbă de la problema inițială.
Algoritmul Divide & Conquer are 3 pași:
- Împărțiți: împărțirea problemei în subprobleme
- Conquer: Rezolvarea recursivă a subproblemelor
- Combinați: combinați soluțiile pentru a obține rezultatul final
Există diferiți algoritmi bazați pe divizarea și cucerirea paradigmei. Sortarea rapidă și sortarea Merge sunt printre ele.
Deși complexitatea în cel mai rău caz al QuickSort este O (n2), care este mai mult decât mulți alți algoritmi de sortare precum Merge Sort și Heap Sort, QuickSort este mai rapid în practică, deoarece bucla sa interioară poate fi implementată eficient pe majoritatea arhitecturilor date din lumea reală.
Să vorbim despre implementarea algoritmului de sortare rapidă. Algoritmii Quicksort iau un element pivot și partiționează matricea din jurul elementului pivot. Există un număr de variații ale Quicksot, care depinde de modul în care alegeți elementul pivot. Există mai multe moduri de a alege elementul pivot:
- Alegerea primului element
- Alegeți ultimul element
- Alegerea unui element aleatoriu
- Alegerea elementului median
Următorul lucru important de înțeles este, funcția partition () în algoritmul de sortare rapidă. Funcția de partiție pentru a lua un element pivot, îl plasează în poziția corectă, mută toate elementele mai mici decât elementul pivot la stânga și toate elementele mai mari la dreapta. Quicksort necesită timp liniar pentru a face acest lucru.
Apoi, matricea este împărțită în două părți din elementul pivot (adică elemente mai mici decât pivot și elemente mai mari decât pivot) și ambele matrice sunt sortate recursiv folosind algoritmul Quicksort.
învățare profundă vs învățare automată vs recunoaștere a modelelor
Acum că înțelegem funcționarea algoritmului QuickSort. Să înțelegem cum să implementăm algoritmul Quicksort în Java.
Sortare rapida Funcţie:
/ * Funcția Quicksort are nevoie ca matricea să fie sortată cu cel mai mic și cel mai mare index * /
void sort (int arr [], int lowIndex, int highIndex) {// Până la lowIndex = highIndex if (lowIndexAcum, să ne uităm la codul de partiționare pentru a înțelege cum funcționează.
Partiție Cod
În codul de partiționare, vom alege ultimul element ca element pivot. Trecem matricea completă (adică folosind variabila j în cazul nostru). Urmărim ultimul cel mai mic element din matrice (adică folosind variabila i în cazul nostru). Dacă găsim un element mai mic decât pivotul, mutăm elementul curent swap a [j] cu arr [i], altfel continuăm să traversăm.
partiție int (int arr [], int lowIndex, int highIndex) {// Realizarea ultimului element ca pivot int pivot = arr [highIndex] // Utilizarea i pentru a urmări elementele mai mici din pivot int i = (lowIndex-1) pentru (int j = lowIndex jAcum, că ați înțeles funcția Quicksort și partiție, să ne uităm rapid la codul complet
Sortare rapida Cod Java
clasa QuickSort {// Metoda partiției int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j// Metoda de sortare
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Metoda de imprimare a matricei
static void printArray (int arr []) {int n = arr.length for (int i = 0 i// Metoda principală
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 ('matrice sortată') printArray (arr)}} Ieșire:
cum se creează pachetul în java
Acum, după executarea programului Java de mai sus, ați fi înțeles cum funcționează QuickSort și cum să-l implementați în Java.Astfel am ajuns la sfârșitul acestui articol despre „Quicksort în Java”. Dacă doriți să aflați mai multe,verificați de Edureka, o companie de învățare online de încredere. Cursul de formare și certificare Java J2EE și SOA al Edureka este conceput pentru a vă instrui atât pentru conceptele Java de bază, cât și pentru cele avansate Java, î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 blog și vă vom răspunde cât mai curând posibil.