Hur fungerar Quicksort-tekniken i Java? - dummies

Här kan du se hur en av de vanligaste sorteringsteknikerna i Java faktiskt fungerar. Denna teknik heter Quicksort, och det är en mycket genial användning av rekursion.

För de flesta av oss kan vi ta reda på hur sorteringsalgoritmer som Quicksort-arbete bara är en intellektuell övning. Java API har sortering som redan är inbyggd.

Quicksort-tekniken sorterar en mängd värden genom att använda recursion. Dess grundläggande steg är således:

1. Välj ett godtyckligt värde som ligger inom intervallet av värden i arrayen.

   Detta värde är pivotpunkten . Det vanligaste sättet att välja pivotpunkten är att helt enkelt välja det första värdet i matrisen. Folk har skrivit doktorsexamen på mer sofistikerade sätt att välja en pivotpunkt som leder till snabbare sortering. Stick med att använda det första elementet i matrisen.

2. Omordna värdena i matrisen så att alla värden som är mindre än svängpunkten ligger på vänstra sidan av matrisen och alla värden som är större än eller lika med svängpunkten ligger på höger sida av array.

   Pivotvärdet anger gränsen mellan vänster och höger sida av matrisen. Det är nog inte dödscentrum, men det spelar ingen roll. Detta steg heter partitionering, och vänster och höger sida av arraysna är partitioner. Behandla nu var och en av de två sektionerna i arrayen som en separat grupp och börja över med steg 1 för den sektionen.

3. Det är den rekursiva delen av algoritmen.

   Den svåraste delen av Quicksort-algoritmen är partitioneringssteget, som måste omorganisera partitionen så att alla värden som är mindre än svängpunkten är till vänster och alla element som är större än svängpunkten punkten är till höger. Antag att matrisen har dessa tio värden:

38 17 58 22 69 31 88 28 86 12

Här är pivotpunkten 38 och uppgiften för partitioneringssteget är att omordna arrayen till något sådant: < 17 12 22 28 31 38 88 69 86 58

Observera att värdena fortfarande är i ordning. Arrayet har emellertid delats runt värdet 38: Alla värden som är mindre än 38 är till vänster om 38 och alla värden som är större än 38 är till höger om 38.

Nu kan du dela upp array in i två partitioner vid värdet 38 och upprepa processen för varje sida. Pivotvärdet själv går med vänstra partitionen, så den vänstra partitionen är så här:

17 12 22 28 31 38

Den här gången väljer uppdelningssteget 17 som svängpunkt och omarrangerar elementen enligt följande: > 12 17 22 28 31 38

Som du kan se är denna del av arrayen sorterad nu.Tyvärr inser Quicksort inte att vid denna tidpunkt så tar det några fler rekursioner för att vara säker. Men det är grundprocessen.