A QuickSort egy divide & conquer algoritmus. A Divide & Conquer algoritmus-tervezési paradigmában rekurzívan osztjuk fel a problémákat az alproblémákban, majd megoldjuk az alproblémákat és végül a megoldásokat egyesítjük a végeredmény megtalálásához. Ebben a cikkben a QuickSort In-re koncentrálunk
A következő hivatkozásokkal foglalkozunk ebben a cikkben,
Kezdjük!
A dolgok részproblémákra bontása során szem előtt kell tartani, hogy az alproblémák szerkezete nem változik az eredeti problémánál fogva.
A Divide & Conquer algoritmus 3 lépésből áll:
- Osztás: A probléma felosztása részproblémákra
- Hódítás: Az alproblémák rekurzív megoldása
- Kombinálás: A megoldások kombinálása a végeredmény megszerzéséhez
Különféle algoritmusok léteznek a divide & conquer paradigmán alapulva. A gyors rendezés és az egyesítés rendezése közé tartozik.
Bár a QuickSort legrosszabb esetben az idő összetettsége O (n2), amely több, mint sok más rendezési algoritmus, mint például a Merge Sort és a Heap Sort, a QuickSort gyorsabb a gyakorlatban, mert belső hurka hatékonyan megvalósítható a legtöbb architektúrán, és a legtöbb valós adatok.
Beszéljünk a Quick sort algoritmus megvalósításáról. A Quicksort algoritmusok egy pivot elemet vesznek fel, és a tömböt a pivot elememt köré osztják. A Quicksotnak számos változata van, amely attól függ, hogy miként választja meg a pivot elemet. A pivot elem többféleképpen választható ki:
- Az első elem kiválasztása
- Válassza ki az utolsó elemet
- Véletlenszerű elem kiválasztása
- Medián elem kiválasztása
A következő fontos megértendő dolog a partíció () függvény a Gyors rendezés algoritmusban. A particionáló függvény egy forgó elem elfogadásához, a megfelelő helyzetbe hozása, az összes, a forgó elemnél kisebb elem balra, az összes nagyobb elem pedig a jobb oldalán mozog. A Quicksort lineáris időt vesz igénybe.
Ezután a tömböt két részre osztják a pivot elemtől (azaz a pivotnál kisebb elemek és a pivotnál nagyobb elemek), és mindkét tömb rekurzívan rendeződik a Quicksort algoritmus segítségével.
java kitör egy módszerből
Most, hogy megértettük a QuickSort algoritmus működését. Értsük meg, hogyan lehet a Quicksort algoritmust Java-ban megvalósítani.
QuickSort Funkció:
/ * A Quicksort függvénynek a tömböt a legalacsonyabb és legmagasabb index alapján kell rendezni
void sort (int arr [], int lowIndex, int highIndex) {// Lig lowIndex = highIndex if (lowIndexMost nézzük meg a particionáló kódot, hogy megértsük a működését.
Partíció Kód
A particionálási kódban az utolsó elemet választjuk ki pivot elemként. Bejárjuk a teljes tömböt (azaz esetünkben a j változót használjuk). Nyomon követjük a tömb utolsó legkisebb elemét (azaz esetünkben az i változót használjuk). Ha találunk a forgásnál kisebb elemet, akkor az a [j] elemet felcseréljük arr [i] -vel, különben tovább haladunk.
int partíció (int arr [], int lowIndex, int highIndex) {// Az utolsó elem elkészítése pivotként int pivot = arr [highIndex] // Az i használatával nyomon követhetjük a kisebb elemeket a pivot int i = (lowIndex-1) for (int j = lowIndex jMost, hogy megértette a Quicksort & partition funkciót, nézzük át gyorsan a teljes kódot
java just in time fordító
QuickSort Java kód
class QuickSort {// Partíciós módszer int partíció (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j// Rendezési módszer
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// A tömb nyomtatásának módszere
static void printArray (int arr []) {int n = arr.length for (int i = 0 i// Fő módszer
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 ('rendezett tömb') printArray (arr)}} Kimenet:
A fenti Java program futtatása után megértette, hogyan működik a QuickSort, és hogyan kell azt Java-ban megvalósítani.Így a „Quicksort a Java-ban” című cikk végéhez értünk. Ha többet szeretne megtudni,nézd meg a Edureka, egy megbízható online tanulási társaság. Az Edureka Java J2EE és SOA képzési és tanúsítási tanfolyamát arra tervezték, hogy mind az alapvető, mind a fejlett Java koncepciókra kiképezzen különféle Java keretrendszereket, például a Hibernate & Spring.
Van egy kérdésünk? Kérjük, említse meg a blog megjegyzés rovatában, és a lehető leghamarabb kapcsolatba lépünk Önnel.