Das Sortieren ist eine der Grundoperationen, die wir an Objekten durchführen. Schon in der Kindheit wird Kindern das Sortieren beigebracht, während sie ihre Denkfähigkeiten entwickeln. Computer und Software sind keine Ausnahme. Es gibt eine große Vielfalt an Sortieralgorithmen in Java.
Ich schlage vor, dass Sie sich ansehen, was sie sind und wie sie funktionieren. Was ist, wenn Sie eines Tages bei einem Vorstellungsgespräch nach einem von ihnen gefragt werden?
Einführung
Das Sortieren von Elementen ist eine der Kategorien von Algorithmen, die ein Entwickler kennen muss. Während zu meiner Schulzeit die Informatik einst nicht ernst genommen wurde, müssen heutige Schüler in der Lage sein, Sortieralgorithmen umzusetzen und zu verstehen.
Grundlegende Algorithmen, die einfachsten, werden mithilfe einer for- Schleife implementiert. Um eine Sammlung von Elementen, beispielsweise ein Array, zu sortieren, müssen Sie die Sammlung natürlich irgendwie durchgehen. Zum Beispiel:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Was lässt sich über diesen Codeabschnitt sagen?
Wir haben eine Schleife, in der wir den Index ( int i) von 0 auf das letzte Element im Array ändern. Tatsächlich nehmen wir einfach jedes Element im Array und geben seinen Inhalt aus. Je mehr Elemente das Array enthält, desto länger dauert die Fertigstellung des Codes. Das heißt, wenn nes sich um die Anzahl der Elemente handelt, n = 10dauert die Ausführung des Programms doppelt so lange wie bei when n = 5.
Wenn unser Programm eine einzige Schleife hat, wächst die Ausführungszeit linear: Je mehr Elemente vorhanden sind, desto länger ist die Ausführungszeit. Es stellt sich heraus, dass der obige Algorithmus in linearer Zeit arbeitet (eine lineare Funktion von n). In solchen Fällen sagen wir, dass die Komplexität des Algorithmus „O(n)“ ist. Diese Notation wird auch „big O“ oder „asymptotisches Verhalten“ genannt. Aber du kannst dich einfach daran erinnern“
Der einfachste Sortieralgorithmus (Blasensortierung)
Angenommen, wir haben ein Array und können es durchlaufen. Großartig. Versuchen wir nun, es in aufsteigender Reihenfolge zu sortieren. Was bedeutet das? Das bedeutet, dass wir bei gegebenen zwei Elementen (z. B. a = 6, b = 5) die Reihenfolge neu anordnen müssen aund bif agrößer als b(if a > b) ist.
Was bedeutet das, wenn wir einen Index verwenden, um mit einer Sammlung zu arbeiten (wie es bei einem Array der Fall ist)? Das heißt, wenn das Element mit Index a größer als das Element mit Index b( array[a] > array[b]) ist, müssen die Elemente vertauscht werden. Es gibt verschiedene Möglichkeiten, den Ort zu wechseln. Aber wir verwenden eine Technik, die einfach, verständlich und leicht zu merken ist:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Jetzt können wir Folgendes schreiben:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Wie Sie sehen, wurden die Elemente tatsächlich vertauscht. Wir haben mit Index 1 begonnen, denn wenn das Array nur ein Element enthält, array[i] < array[i-1]ist der Ausdruck für Index ungültig 0. Dies schützt uns auch vor Fällen, in denen das Array keine oder nur ein Element enthält, und sorgt dafür, dass der Code besser aussieht.
Das resultierende Array ist jedoch immer noch nicht sortiert, da ein Durchgang nicht ausreicht, um die Sortierung durchzuführen. Wir müssen eine weitere Schleife hinzufügen, in der wir immer wieder Durchgänge durchführen, bis wir ein sortiertes Array erhalten:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Also haben wir unseren ersten Sortieralgorithmus fertiggestellt. Wir wiederholen die äußere Schleife ( while), bis wir entscheiden, dass keine weiteren Iterationen erforderlich sind. Standardmäßig gehen wir vor jeder neuen Iteration davon aus, dass unser Array sortiert ist und wir keine Schleife mehr durchführen müssen. Dementsprechend bewegen wir uns nacheinander durch die Elemente und überprüfen diese Annahme.
Wenn die Elemente jedoch nicht in der richtigen Reihenfolge sind, tauschen wir die Elemente aus und verstehen, dass wir jetzt keine Garantie dafür haben, dass die Elemente in der richtigen Reihenfolge sind. Das bedeutet, dass wir eine weitere Iteration durchführen müssen. Nehmen wir zum Beispiel an, wir haben [3, 5, 2]. 5ist mehr als 3– alles ist gut. Ist aber 2kleiner als 5. Allerdings [3, 2, 5]ist da ein weiterer Durchgang erforderlich3 > 2und sie müssen ausgetauscht werden. Da wir eine Schleife innerhalb einer Schleife verwenden, erhöht sich die Komplexität unseres Algorithmus. Bei gegebenen nElementen wird es zu n * n, das heißt O(n^2).
Dies nennt man quadratische Komplexität. Im Allgemeinen können wir nicht genau wissen, wie viele Iterationen erforderlich sein werden. Der Ausdruck der Komplexität eines Algorithmus zeigt, wie die Komplexität im schlimmsten Fall zunimmt. Das heißt, es gibt an, um wie viel sich die Ausführungszeit erhöht, wenn sich die Anzahl der Elemente nändert. Die Blasensortierung ist einer der einfachsten und ineffizientesten Sortieralgorithmen. Manchmal wird es auch als „dumme Sorte“ bezeichnet. Material zu diesem Thema:
Ein weiterer Sortieralgorithmus ist die Auswahlsortierung. Es hat auch quadratische Komplexität, aber dazu später mehr. Die Idee ist also einfach. Bei jedem Durchgang wählen wir das kleinste Element aus und verschieben es an den Anfang. Zusätzlich beginnt jeder Durchgang einen Schritt nach rechts. Mit anderen Worten: Der erste Durchgang beginnt beim nullten Element, der zweite Durchgang beim ersten usw. Es sieht folgendermaßen aus:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Diese Sortierung ist instabil, da identische Elemente (in Bezug auf die Eigenschaften, die wir zum Sortieren der Elemente verwenden) ihre relativen Positionen ändern können. Ein gutes Beispiel finden Sie im Wikipedia-Artikel zur Auswahlsortierung . Material zu diesem Thema:
Auch die Einfügungssortierung hat quadratische Komplexität, da wir wieder eine Schleife innerhalb einer Schleife haben. Was macht die Einfügungssortierung anders?
Dieser Sortieralgorithmus ist „stabil“. Dies bedeutet, dass identische Elemente ihre relative Reihenfolge nicht ändern. Auch hier meinen wir identisch in Bezug auf die Merkmale, nach denen wir sortieren.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Shuttle-Sortierung
Es gibt einen weiteren einfachen Sortieralgorithmus: Shuttle-Sortierung. Dies wird auch als bidirektionale Blasensorte oder Cocktail-Shaker-Sorte bezeichnet. Diese alternativen Namen sagen uns, dass es bei der Shuttle-Variante nicht um das Space Shuttle geht. Es geht um etwas, das sich hin und her bewegt.
Das können Sie sich vorstellen, wenn Sie an diesen Algorithmus denken. Was ist die Essenz des Algorithmus? Der Kern des Algorithmus besteht darin, dass wir von links nach rechts iterieren, Elemente austauschen und prüfen, ob in der anderen Richtung verbleibende Elemente ausgetauscht werden müssen.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Ein weiterer einfacher Sortieralgorithmus ist die Shell-Sortierung. Der Kern davon ähnelt der Blasensortierung, aber in jeder Iteration haben wir eine andere Lücke zwischen den verglichenen Elementen. Es wird mit jeder Iteration halbiert. Hier ist eine Implementierung:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Neben diesen einfachen Sortieralgorithmen gibt es auch kompliziertere Sortieralgorithmen. Beispiel: Zusammenführungssortierung. Es gibt zwei Dinge zu beachten. Erstens kommt uns hier die Rekursion zu Hilfe. Zweitens ist die Komplexität des Algorithmus nicht mehr quadratisch, wie wir es gewohnt sind.
Die Komplexität dieses Algorithmus ist logarithmisch. Dies wird als geschrieben O(n log n). Also lasst es uns umsetzen. Zuerst schreiben wir einen rekursiven Aufruf der Sortiermethode:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Fügen wir nun die Hauptaktion zu unserer Implementierung hinzu. Hier ist unsere Super-Methode:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Wir können unser Beispiel durch Aufrufen ausführenmergeSort(array, 0, array.length-1). Wie Sie sehen, läuft der Prozess darauf hinaus, ein Eingabearray zusammen mit Angaben zum Anfang und Ende des Abschnitts zu akzeptieren, der sortiert werden muss. Wenn die Sortierung beginnt, sind dies der Anfang und das Ende des Arrays.
Dann berechnen wir das Trennzeichen, das den Index darstellt, an dem wir das Array aufteilen. Wenn das Array in zwei Teile geteilt werden kann, dann rufen wir die Sortiermethode rekursiv für die beiden Hälften des Arrays auf. Wir bereiten einen Hilfspuffer vor, in den wir den sortierten Abschnitt einfügen. Als nächstes setzen Sie den Index an den Anfang des zu sortierenden Abschnitts und beginnen mit dem Durchlaufen jedes Elements des leeren Puffers, wobei Sie ihn mit den kleinsten Elementen füllen.
Wenn das Element, auf das der Index zeigt, kleiner ist als das Element, auf das das Trennzeichen zeigt, legen wir das Element in den Puffer und verschieben den Index. Ansonsten, Wir platzieren das Element, auf das das Trennzeichen zeigt, im Puffer und verschieben das Trennzeichen. Sobald das Trennzeichen über die Grenzen des zu sortierenden Abschnitts hinausgeht oder wir das gesamte Array füllen, gilt der angegebene Bereich als sortiert.Material zu diesem Thema:
Ein weiterer interessanter Sortieralgorithmus ist die Zählsortierung. Die algorithmische Komplexität beträgt hier O(n+k)die nAnzahl der Elemente und kder Maximalwert eines Elements. Dieser Algorithmus hat jedoch einen Nachteil: Wir müssen die minimalen und maximalen Werte im Array kennen. Hier ist ein Beispiel für die Zählsortierung:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Sie können verstehen, dass es sehr unpraktisch ist, wenn wir die Mindest- und Höchstwerte im Voraus kennen müssen. Und wir haben hier einen weiteren Algorithmus: Radix-Sortierung. Ich werde den Algorithmus hier nur visuell vorstellen. Siehe die ergänzenden Materialien zur Umsetzung: Materialien:
Nun ist es Zeit für den Nachtisch – Quick Sort, einer der bekanntesten Sortieralgorithmen. Es hat eine logarithmische Komplexität: O(n log n). Dieser Sortieralgorithmus wurde von Tony Hoare entwickelt. Interessanterweise erfand er es, als er in der Sowjetunion lebte, wo er an der Moskauer Universität maschinelle Übersetzung studierte und einen Russisch-Englisch-Sprachführer entwickelte.
Darüber hinaus verwendet Java eine komplexere Version dieses Algorithmus in Arrays.sort. Was ist mit Collections.sort? Werfen Sie doch mal einen Blick darauf, wie es „unter der Haube“ zugeht. Hier ist der Code:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Das ist alles sehr beängstigendes Zeug, also lasst uns näher darauf eingehen.
Für das Eingabearray ( int[]Quelle) erstellen wir zwei Markierungen: links ( L) und rechts ( R). Beim ersten Methodenaufruf entsprechen sie dem Anfang und Ende des Arrays.
Dann identifizieren wir das Pivot-Element, das treffend benannt ist pivot. Danach besteht unsere Aufgabe darin, kleinere Werte nach pivotlinks pivotund größere nach rechts zu verschieben.
Dazu bewegen wir zunächst den LMarker, bis wir einen Wert größer als finden pivot. Wenn kein kleinerer Wert gefunden wird, dann L wird gleich pivot.
Dann verschieben wir den RMarker, bis wir einen Wert kleiner als finden pivot. Wenn kein größerer Wert gefunden wird, Rwird er gleich pivot.
Wenn der LMarker vor dem RMarker liegt oder mit ihm übereinstimmt, versuchen wir als nächstes, die Elemente zu vertauschen, wenn das LElement kleiner als das RElement ist.
Dann verschieben wir Lum 1 nach rechts und Rum 1 nach links.
Wenn sich die LMarkierung über die RMarkierung hinaus bewegt, bedeutet dies, dass der Austausch abgeschlossen ist: Kleinere Werte befinden sich links von pivot, größere Werte rechts vonpivot.
Danach rufen wir die gleiche Sortiermethode rekursiv für die Subarrays auf – vom Anfang des zu sortierenden Abschnitts bis zur rechten Markierung und von der linken Markierung bis zum Ende des zu sortierenden Abschnitts. Warum vom Anfang bis zur rechten Markierung? Denn am Ende einer Iteration stellt sich heraus, dass sich der rechte Marker so weit bewegt, dass er zur Grenze des linken Teils wird. Dieser Algorithmus ist komplexer als die einfache Sortierung, daher ist es am besten, ihn zu skizzieren. Nehmen Sie ein weißes Blatt Papier und schreiben Sie: 4 2 6 7 3. Schreiben Sie dann pivotin die Mitte, also unter die Zahl 6. Kreisen Sie es ein.
Schreiben Sie unter 4 Lund unter 3 R. 4 weniger als 6, 2 weniger als 6. Am Ende bewegen wir uns Lauf die
pivotPosition, weil Lwir nicht daran vorbeikommen könnenpivot, je nach Zustand.
Schreiben Sie noch einmal 4 2 6 7 3. Kreisen Sie 6 ein (pivot) und legen Sie Ldarunter. Verschieben Sie nun die
RMarkierung.
3 ist kleiner als 6, also setzen Sie den RMarker auf 3. Da 3 kleiner als 6 ist (pivot), führen wir einen aus swap.
Schreiben Sie das Ergebnis: 4 2 3 7 6. Kreisen Sie 6 ein, weil es immer noch das ist pivot.
Der LMarker ist auf 3. Der RMarker ist auf 6. Denken Sie daran, dass wir die Marker verschieben, bis Lwir darüber hinausgehen R. Gehen Sie Lzur nächsten Nummer.
Hier möchte ich zwei Möglichkeiten untersuchen: 1) den Fall, in dem die vorletzte Zahl 7 ist, und 2) den Fall, in dem sie 1 und nicht 7 ist.
Wenn die vorletzte Zahl 1 ist: Bewegen Sie die LMarkierung auf 1, weil wir uns bewegen können Lsolange die LDer Marker zeigt auf eine Zahl kleiner als pivot. Aber wir können nicht Rvon 6 weggehen, weil wir R nur bewegen können, wenn der RMarker auf eine Zahl zeigt, die größer als ist pivot. Wir führen kein aus swap, da 1 kleiner als 6 ist. Schreiben Sie die aktuelle Situation: 4 2 3 1 6. Kreisen Sie 6 ein (pivot). Lverschiebt sich vorbei pivotund bleibt stehen.
Rbewegt sich nicht. Wir führen keinen Tausch durch. Verschieben Lund Rum eine Position. Schreiben Sie die
RMarkierung unter 1. Die LMarkierung ist außerhalb der Grenzen. Weil Les außerhalb der Grenzen liegt, unternehmen wir nichts. Aber wir schreiben wieder 4 2 3 1, weil dies unsere linke Seite ist, die kleiner als pivot(6) ist. Wählen Sie das Neue aus
pivotund beginnen Sie alles erneut :)
Wenn die vorletzte Zahl 7 ist:Verschieben Sie die LMarkierung auf 7. Wir können die rechte Markierung nicht verschieben, da sie bereits auf den Drehpunkt zeigt. 7 ist größer als pivot, also führen wir eine aus swap. Schreiben Sie das Ergebnis: 4 2 3 6 7. Kreisen Sie 6 ein, weil es das ist pivot. Der LMarker wird jetzt auf 7 verschoben, und der RMarker wird auf 3 verschoben. Es macht keinen Sinn, den Teil vom LEnde her zu sortieren, da es nur 1 Element gibt. Allerdings schicken wir das Teil von 4 Rzur Sortierung an den Marker. Wir wählen a pivotund fangen von vorne an :)
Auf den ersten Blick mag es so aussehen, als ob, wenn man viele Werte addiert, gleich istpivot, dann brechen Sie den Algorithmus. Aber das ist nicht der Fall. Sie können sich knifflige Kombinationen ausdenken und sich auf dem Papier davon überzeugen, dass alles richtig ist, und sich wundern, dass solch einfache Aktionen einen so zuverlässigen Sortiermechanismus implementieren. Der einzige Nachteil ist, dass dieser Sortieralgorithmus nicht stabil ist. Denn ein Austausch kann die relative Reihenfolge identischer Elemente ändern, wenn eines von ihnen zuvor angetroffen wird, pivotbevor das andere Element in den Teil davor vertauscht wird pivot.
Das Endergebnis
Oben haben wir uns einen „Gentleman“-Satz von in Java implementierten Sortieralgorithmen angesehen. Algorithmen sind im Allgemeinen nützlich, sowohl aus angewandter Sicht als auch im Hinblick auf das Erlernen des Denkens. Manche sind einfacher, manche komplizierter. Für einige haben kluge Leute ihre Dissertationen verteidigt. Für andere haben sie superdicke Bücher geschrieben.
Ich hoffe, dass die ergänzenden Materialien Ihnen dabei helfen, noch mehr zu lernen, da es sich bei diesem Artikel nur um einen Überblick handelt, der sich bereits als gewichtig erwiesen hat. Und sein Zweck ist es, eine kleine Einführung zu geben. Eine Einführung in Algorithmen finden Sie auch, wenn Sie
„Grokking-Algorithmen “ lesen.
Mir gefällt auch die Playlist von Jack Brown:AQA Decision 1 1.01 Tracing an Algorithm .
Zum Spaß können Sie beim Sortieren Algorithmen visualisierungen sehen sorting.at und visualgo.net.
Volodymyr is one of those who learned Java development thanks to the CodeGym course, and after studying, got a job in our company. ...
[Vollständige Biografie lesen]
GO TO FULL VERSION