Video: Algoritm pentru cautarea binara in C++ 2024
Aici puteți afla cum funcționează de fapt una dintre cele mai utilizate tehnici de sortare din Java. Această tehnică este numită Quicksort, și este o utilizare foarte ingenioasă a recursivității.
Pentru majoritatea dintre noi, imaginind modul în care algoritmii de sortare, cum ar fi munca Quicksort, este doar un exercițiu intelectual. API-ul Java are deja o structură de sortare.
Tehnica Quicksort sortează o serie de valori utilizând recursul. Pașii lui de bază sunt astfel:
-
Alegeți o valoare arbitrară care se află în intervalul de valori din matrice.
Această valoare este punctul de pivotare . Cea mai obișnuită modalitate de a alege punctul de pivotare este alegerea primei valori din matrice. Oamenii au scris grade de doctorat pe metode mai sofisticate de a alege un punct de pivotare care are ca rezultat o sortare mai rapidă. Stick cu utilizarea primului element din matrice.
-
Rearanjați valorile din matrice astfel încât toate valorile care sunt mai mici decât punctul de pivotare să fie în partea stângă a matricei și toate valorile care sunt mai mari sau egale cu punctul de pivotare sunt în partea dreaptă a matrice.
Valoarea pivotului indică limita dintre partea stângă și partea dreaptă a matricei. Probabil că nu va fi mort, dar nu contează. Acest pas este numit partiționare, iar părțile stângi și drepte ale array-urilor sunt partiții.
-
Acum tratați fiecare din cele două secțiuni ale matricei ca o matrice separată și începeți cu Pasul 1 pentru acea secțiune.
Aceasta este partea recursivă a algoritmului.
Partea cea mai grea a algoritmului Quicksort este etapa de partiționare, care trebuie să rearanjeze partiția astfel încât toate valorile care sunt mai mici decât punctul de pivotare să fie la stânga și toate elementele care sunt mai mari decât pivotul punct sunt pe dreapta. Să presupunem că matricea are aceste zece valori:
38 17 58 22 69 31 88 28 86 12
Aici punctul de pivotare este 38, iar sarcina pasului de partiționare este de a rearanja matricea la ceva de genul: 17 12 22 28 31 38 88 69 86 58
Rețineți că valorile sunt încă nefuncționale. Totuși, matricea a fost împărțită în jurul valorii de 38: Toate valorile care sunt mai mici de 38 sunt la stânga de 38 și toate valorile care sunt mai mari de 38 sunt la dreapta lui 38.
Acum puteți împărți array în două partiții la valoarea 38 și repetați procesul pentru fiecare parte. Numai pivotul merge cu partiția din stânga, astfel încât partiția stângă este aceasta:
17 12 22 28 31 38
De această dată, etapa de partiționare alege 17 ca punct de pivotare și rearanjează elementele după cum urmează: > 12 17 22 28 31 38
După cum puteți vedea, această porțiune a matricei este sortată acum.Din nefericire, Quicksort nu-și dă seama că în acest moment, deci este nevoie de câteva recursuri pentru a fi sigur. Dar acesta este procesul de bază.
