Shell Sorteren in Java
1. Inleiding
In deze zelfstudie beschrijven we het Shell-sorteeralgoritme in Java.
2. Overzicht van Shell Sorteren
2.1. Omschrijving
Laten we eerst het Shell-sorteeralgoritme beschrijven, zodat we weten wat we proberen te implementeren.
Shell-sortering is gebaseerd op het invoegingssorteeralgoritme en behoort tot de groep van zeer efficiënte algoritmen. Over het algemeen, het algoritme verdeelt een originele set in kleinere subsets en vervolgens wordt elk van deze gesorteerd met behulp van invoegsortering.
Maar hoe het de subsets maakt, is niet eenvoudig. Het kiest geen aangrenzende elementen om een subset te vormen, zoals we zouden verwachten. In plaats daarvan gebruikt shell-sortering het zogenaamde interval of kloof voor het maken van subsets. Als we bijvoorbeeld de kloof hebben ik, betekent dit dat een subset de elementen bevat die zijn ik posities uit elkaar.
Ten eerste sorteert het algoritme de elementen die ver van elkaar verwijderd zijn. Vervolgens wordt de opening kleiner en worden dichterbij liggende elementen vergeleken. Op deze manier kunnen sommige elementen die niet op de juiste positie staan, sneller worden gepositioneerd dan wanneer we de subsets zouden maken uit de aangrenzende elementen.
2.2. Een voorbeeld
Laten we dit eens bekijken in het voorbeeld met de hiaten van 3 en 1 en de ongesorteerde lijst van 9 elementen:
Als we de bovenstaande beschrijving volgen, hebben we in de eerste iteratie drie subsets met 3 elementen (gemarkeerd door dezelfde kleur):
Na het sorteren van elk van de subsets in de eerste iteratie, ziet de lijst er als volgt uit:
We kunnen opmerken dat, hoewel we nog geen gesorteerde lijst hebben, de elementen nu dichter bij de gewenste posities staan.
Ten slotte moeten we nog een sortering doen met een toename van één en het is eigenlijk een eenvoudige invoegsortering. Het aantal verschuivingsbewerkingen dat we moeten uitvoeren om een lijst te sorteren, is nu kleiner dan het geval zou zijn als we de eerste iteratie niet zouden uitvoeren:
2.3. De tussenruimtesequenties kiezen
Zoals we al zeiden, heeft de shell-sortering een unieke manier om gap-sequenties te kiezen. Dit is een moeilijke taak en we moeten oppassen dat we niet te weinig of te veel hiaten kiezen. Meer details zijn te vinden in de lijst met meest voorgestelde gap-sequenties.
3. Implementatie
Laten we nu eens kijken naar de implementatie. We gebruiken de originele volgorde van Shell voor intervalverhogingen:
N / 2, N / 4, ..., 1 (continu delen door 2)De implementatie zelf is niet al te ingewikkeld:
openbare ongeldige sortering (int arrayToSort []) {int n = arrayToSort.length; for (int gap = n / 2; gap> 0; gap / = 2) {for (int i = gap; i = gap && arrayToSort [j - gap]> key) {arrayToSort [j] = arrayToSort [j - gap ]; j - = opening; } arrayToSort [j] = sleutel; }}}We hebben eerst een gap-reeks gemaakt met een for-lus en vervolgens hebben we de invoegsortering voor elke gap-maat uitgevoerd.
Nu kunnen we onze methode eenvoudig testen:
@Test openbare leegte gegevenUnsortedArray_whenShellSort_thenSortedAsc () {int [] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort (invoer); int [] verwacht = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals ("de twee arrays zijn niet gelijk", verwacht, invoer); }4. Complexiteit
Over het algemeen, het Shell-sorteeralgoritme is zeer efficiënt met middelgrote lijsten. De complexiteit is moeilijk te bepalen omdat het sterk afhangt van de gap-sequentie, maar de tijdcomplexiteit varieert tussen AAN) en O (N ^ 2).
De complexiteit van de ruimte in het slechtste geval is AAN) met O (1) hulpruimte.
5. Conclusie
In deze tutorial hebben we Shell-sortering beschreven en geïllustreerd hoe we het in Java kunnen implementeren.
Zoals gewoonlijk was de volledige code te vinden op GitHub.
