Entwicklungsprojekte nutzen häufiger verschiedene Algorithmen, als Sie vielleicht denken. Angenommen, wir müssen einige Daten nach bestimmten Parametern (Spalten) sortieren, damit wir ohne großen Aufwand durch die Daten navigieren können. Es wäre also nicht verwunderlich, wenn ein Vorstellungsgesprächspartner Sie nach einem bestimmten Grundalgorithmus fragen und Ihnen vielleicht die Aufgabe geben würde, ihn mithilfe von Code zu implementieren. Und da Sie auf dieser Website sind, gehe ich mal davon aus, dass Sie in Java schreiben. Aus diesem Grund empfehle ich Ihnen heute, sich mit einigen grundlegenden Algorithmen und konkreten Beispielen für deren Implementierung in Java vertraut zu machen. Mit „einige“ meine ich:
Übersicht über Array-Sortieralgorithmen:
Blasensortierung,
Auswahlsortierung,
Sortieren durch Einfügen,
Muschelsortierung,
schnelle Sorte,
Zusammenführen, sortieren,
Gierige Algorithmen
Pfadfindungsalgorithmen
Tiefensuche
Breitensuche
Dijkstras Shortest Path First-Algorithmus
Nun, ohne weitere Umschweife, kommen wir zur Sache.
1. Übersicht über Sortieralgorithmen
Blasensortierung
Dieser Sortieralgorithmus ist vor allem für seine Einfachheit bekannt, allerdings ist er auch einer der langsamsten. Betrachten wir als Beispiel eine Blasensortierung für Zahlen in aufsteigender Reihenfolge. Stellen wir uns eine zufällige Zahlenfolge vor. Wir führen die folgenden Schritte für diese Zahlen aus, beginnend am Anfang der Sequenz:
vergleiche zwei Zahlen;
Wenn die Zahl links größer ist, tauschen Sie sie aus.
eine Position nach rechts verschieben.
Nachdem wir diese Schritte für die gesamte Folge ausgeführt haben, werden wir feststellen, dass die größte Zahl am Ende unserer Zahlenreihe steht. Dann durchlaufen wir die Sequenz erneut und führen dabei genau die gleichen Schritte wie oben aus. Aber dieses Mal werden wir das letzte Element der Liste nicht einbeziehen, da es die größte Zahl ist und sich beim Sortieren der Zahlen bereits genau dort befindet, wo es sein sollte. Auch hier verschieben wir am Ende die nächstgrößere Zahl an das Ende unserer Sequenz. Das bedeutet natürlich, dass die beiden größten Zahlen an ihrem richtigen Platz stehen. Wieder durchlaufen wir die Sequenz und schließen dabei die Elemente aus, die sich bereits an ihrem Platz befinden, bis alle Elemente in der erforderlichen Reihenfolge sind. Schauen wir uns an, wie die Blasensortierung im Java-Code implementiert wird:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
Wie Sie sehen, gibt es hier nichts Kompliziertes. Alles scheint einfach großartig zu sein, und das wäre es auch, wenn da nicht ein Manko wäre – die Blasensortierung ist sehr, sehr langsam. Die Zeitkomplexität beträgt O(N²), da wir verschachtelte Schleifen haben. Die äußere Schleife über die Elemente wird N-mal ausgeführt. Die innere Schleife wird ebenfalls N-mal ausgeführt. Als Ergebnis erhalten wir N*N oder N² Iterationen.
Auswahlsortierung
Dieser Algorithmus ähnelt der Blasensortierung, arbeitet jedoch etwas schneller. Nehmen wir als Beispiel noch einmal eine Zahlenfolge, die wir in aufsteigender Reihenfolge anordnen möchten. Die Essenz dieses Algorithmus besteht darin, nacheinander alle Zahlen zu durchlaufen und das kleinste Element auszuwählen, das wir nehmen und mit dem Element ganz links (dem 0. Element) austauschen. Hier haben wir eine ähnliche Situation wie bei der Blasensortierung, aber in diesem Fall ist unser sortiertes Element das kleinste. Daher beginnt der nächste Durchlauf durch die Elemente bei dem Element mit Index 1. Wir wiederholen diese Durchgänge, bis alle Elemente sortiert sind. Implementierung in Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
Dieser Algorithmus ist der Blasensortierung überlegen, da hier die Anzahl der erforderlichen Verschiebungen von O(N²) auf O(N) reduziert wird. Wir durchlaufen nicht ein Element durch die gesamte Liste, aber die Anzahl der Vergleiche beträgt immer noch O(N²).
Sortieren durch Einfügen
Wir betrachten noch eine weitere Zahlenfolge, die wir in aufsteigender Reihenfolge anordnen möchten. Dieser Algorithmus besteht darin, eine Markierung zu platzieren, wobei alle Elemente links von der Markierung bereits teilweise untereinander sortiert sind. Bei jedem Schritt des Algorithmus wird eines der Elemente ausgewählt und an der gewünschten Position in der teilweise sortierten Reihenfolge platziert. Somit wächst der sortierte Teil, bis alle Elemente untersucht wurden. Fragen Sie sich, wie Sie die Teilmenge der bereits sortierten Elemente erhalten und wie wir bestimmen, wo die Markierung platziert werden soll? Aber das Array, das aus dem ersten Element besteht, ist doch schon sortiert, nicht wahr? Werfen wir einen Blick auf die Implementierung in Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
Diese Art der Sortierung ist den oben beschriebenen überlegen, da dieser Algorithmus trotz der gleichen O(N²)-Laufzeit doppelt so schnell wie die Blasensortierung und etwas schneller als die Auswahlsortierung ist.
Muschelsortierung
Bei dieser Sortierung handelt es sich im Wesentlichen um eine modifizierte Einfügungssortierung. Wovon rede ich? Stellen wir das Wichtigste an die erste Stelle. Wir müssen zuerst ein Intervall wählen. Es gibt viele Ansätze, diese Wahl zu treffen. Wir werden hierauf nicht zu sehr ins Detail gehen. Teilen wir unser Array in zwei Hälften und erhalten eine Zahl – dies wird unser Intervall sein. Wenn wir also 9 Elemente in unserem Array haben, beträgt unser Intervall 9/2 = 4,5. Wir verwerfen den Bruchteil und erhalten 4, da Array-Indizes nur ganze Zahlen sein können. Wir werden diese Zeit nutzen, um unsere Gruppen zu bilden. Wenn ein Element den Index 0 hat, ist der Index des nächsten Elements in seiner Gruppe 0+4, also 4. Das dritte Element hat den Index 4+4, das vierte – 8+4 und so weiter. In der zweiten Gruppe wird das erste Element 1,5,9 sein... In der dritten und vierten Gruppe wird die Situation dieselbe sein. Infolge, Aus dem Zahlenarray {6,3,8,8,6,9,4,11,1} erhalten wir vier Gruppen: I — {6,6,1} II — {3,9} III — {8,4 } IV – {8,11} Sie behalten ihre Plätze im allgemeinen Array, aber wir haben sie als Mitglieder derselben Gruppe markiert: {6,3,8,8,6,9,4,11,1} Als nächstes folgt die Einfügung Die Sortierung wird auf diese Gruppen angewendet und sie sehen dann wie folgt aus: I – {1,6,6} II – {3,9} III – {4,8} IV – {8,11} Im allgemeinen Array sind die Die von den Gruppen besetzten Zellen bleiben gleich, aber ihre interne Reihenfolge ändert sich entsprechend der Reihenfolge der oben genannten Gruppen: {1,3,4,8,6,9,8,11,6} Das Array ist zu a geworden etwas geordneter, nicht wahr? Das nächste Intervall wird durch 2 geteilt: 4/2 = 2 Wir haben zwei Gruppen: I — {1,4,6,8,6} II — {3,8,9,11} Im allgemeinen Array haben wir : {1,3,4,8,6,9,8,11,6} Wir führen den Einfügungssortierungsalgorithmus für beide Gruppen aus und erhalten dieses Array: {1,3,4,8,6,9,6, 11, 8} Jetzt ist unser Array fast sortiert. Wir müssen eine letzte Iteration des Algorithmus durchführen: Wir teilen das Intervall durch 2: 2/2 = 1. Wir erhalten eine Gruppe, die aus dem gesamten Array besteht: {1,3,4,8,6,9,6,11 ,8} Wenn wir den Einfügungssortierungsalgorithmus darauf ausführen, erhalten wir: {1,3,4,6,6,8,8,9,11} Schauen wir uns an, wie wir diese Sortierung in Java-Code zum Leben erwecken können:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
Derzeit ist die Leistung von Shellsort nicht einfach zu charakterisieren, da die Ergebnisse in verschiedenen Situationen unterschiedlich sind. Experimentelle Schätzungen reichen von O(N 3/2 ) bis O(N 7/6 ).
Schnelle Sorte
Dies ist einer der beliebtesten Algorithmen, daher lohnt es sich, ihm besondere Aufmerksamkeit zu schenken. Der Kern dieses Algorithmus besteht darin, dass ein Pivotelement in einer Liste von Elementen ausgewählt wird. Wir sortieren alle anderen Elemente relativ zum Pivot-Element. Werte, die kleiner als das Pivot-Element sind, stehen auf der linken Seite. Werte größer als rechts. Als nächstes werden im rechten und linken Teil auch Pivot-Elemente ausgewählt, und das Gleiche passiert: Die Werte werden relativ zu diesen Elementen sortiert. Dann werden in den neu gebildeten Teilen Pivot-Elemente ausgewählt und so weiter, bis wir eine sortierte Reihenfolge erhalten. Die folgende Java-Implementierung dieses Algorithmus verwendet Rekursion:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
Zweifellos ist der Quicksort-Algorithmus der beliebteste, da er in den meisten Situationen schneller läuft als andere. Seine zeitliche Komplexität beträgt O(N*logN).
Zusammenführen, sortieren
Auch diese Sorte ist beliebt. Es ist einer von vielen Algorithmen, der auf dem Prinzip „Teile und herrsche“ basiert. Solche Algorithmen unterteilen das Problem zunächst in überschaubare Teile (Quicksort ist ein weiteres Beispiel für einen solchen Algorithmus). Was ist also der Kern dieses Algorithmus?
Teilen:
Das Array ist in zwei etwa gleich große Teile aufgeteilt. Jeder dieser beiden Teile wird in zwei weitere geteilt und so weiter, bis die kleinstmöglichen unteilbaren Teile übrig bleiben. Die kleinsten unteilbaren Teile haben wir, wenn jedes Array ein Element hat, also ein Array, das bereits sortiert ist.
Erobern:
Hier beginnen wir mit dem Prozess, der dem Algorithmus seinen Namen gab: Merge. Dazu nehmen wir die beiden resultierenden sortierten Arrays und führen sie zu einem zusammen. In diesem Fall wird das kleinste der ersten Elemente der beiden Arrays in das resultierende Array geschrieben. Dieser Vorgang wird wiederholt, bis alle Elemente in diesen beiden Arrays kopiert wurden. Das heißt, wenn wir zwei minimale Arrays {6} und {4} haben, vergleichen wir ihre Werte und generieren dieses zusammengeführte Ergebnis: {4,6}. Wenn wir die Arrays {4,6} und {2,8} sortiert haben, vergleichen wir zuerst die Werte 4 und 2 und schreiben dann 2 in das resultierende Array. Danach werden 4 und 8 verglichen und wir schreiben 4. Schließlich werden 6 und 8 verglichen. Dementsprechend schreiben wir 6 und erst danach 8. Als Ergebnis erhalten wir das folgende zusammengeführte Array: {2,4,6,8}. Wie wird das im Java-Code aussehen? Um diesen Algorithmus auszuführen, ist es für uns praktisch, die Rekursion zu verwenden:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
Wie bei der Schnellsortierung verschieben wir die rekursive Methode in eine Zwischenmethode, sodass der Benutzer nur das zu sortierende Array angeben muss und sich nicht um die Bereitstellung zusätzlicher Standardargumente kümmern muss. Dieser Algorithmus weist Ähnlichkeiten mit Quicksort auf, und es überrascht nicht, dass seine Ausführungsgeschwindigkeit dieselbe ist: O(N*logN).
2. Gierige Algorithmen
Ein Greedy-Algorithmus ist ein Ansatz, bei dem in jeder Phase lokal optimale Entscheidungen getroffen werden, mit der Annahme, dass die endgültige Lösung auch optimal sein wird. Die „optimale“ Lösung ist diejenige, die in einem bestimmten Schritt/Stadium den offensichtlichsten und unmittelbarsten Nutzen bietet. Um diesen Algorithmus zu untersuchen, nehmen wir ein ziemlich häufiges Problem – das Rucksackproblem. Stellen Sie sich für einen Moment vor, Sie wären ein Dieb. Sie sind nachts mit einem Rucksack (Rucksack) in ein Geschäft eingebrochen. Vor Ihnen liegen mehrere Waren, die Sie stehlen könnten. Aber gleichzeitig ist das Fassungsvermögen Ihres Rucksacks begrenzt. Es kann nicht mehr als 30 Gewichtseinheiten tragen. Sie möchten auch die wertvollsten Gegenstände mitnehmen, die in den Rucksack passen. Wie bestimmen Sie, was Sie in Ihre Tasche packen? So,
Wählen Sie den teuersten Artikel, der noch nicht vergeben ist.
Wenn es in den Rucksack passt, stecken Sie es hinein. Wenn nicht, dann lassen Sie es.
Haben wir schon alles gestohlen? Wenn nicht, kehren wir zu Schritt 1 zurück. Wenn ja, verlassen wir schnell den Laden, da wir das erreicht haben, wozu wir gekommen sind.
Schauen wir uns das an, aber in Java. So sieht die Item-Klasse aus:
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
Hier gibt es nichts Besonderes: drei Felder (Name, Gewicht, Wert), die die Eigenschaften des Artikels definieren. Wie Sie sehen können, ist außerdem die Comparable-Schnittstelle implementiert, damit wir unsere Artikel nach Preis sortieren können. Als nächstes schauen wir uns die Bag-Klasse an, die unseren Rucksack darstellt:
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
maxWeight ist die Kapazität unseres Rucksacks, die festgelegt wird, wenn wir ein Objekt erstellen;
items stellt die Objekte in unserem Rucksack dar;
currentWeight , currentValue – diese Felder speichern das aktuelle Gewicht und den aktuellen Wert aller Artikel im Rucksack, die wir erhöhen, wenn wir in der Methode addItem einen neuen Artikel hinzufügen.
Wie auch immer, gehen wir jetzt zu der Klasse, in der die ganze Aktion stattfindet:
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
Zuerst erstellen wir eine Liste mit Elementen und sortieren sie. Wir erstellen ein Taschenobjekt mit einer Kapazität von 30 Einheiten. Als nächstes übergeben wir die Artikel und das Taschenobjekt an die Methode fillBackpack, die den Rucksack gemäß unserem Greedy-Algorithmus füllt:
Es ist ziemlich einfach: Wir gehen zunächst eine Liste der Artikel durch, sortiert nach Kosten, und legen sie in die Tasche, sofern das Fassungsvermögen dies zulässt. Wenn nicht genügend Platz vorhanden ist, wird das Element übersprungen und wir durchlaufen die restlichen Elemente weiter, bis wir das Ende der Liste erreichen. Sobald wir main ausführen, erhalten wir folgende Konsolenausgabe:
Das Gewicht des Rucksacks beträgt 29. Der Gesamtwert der Gegenstände im Rucksack beträgt 3700
Dies ist ein Beispiel für einen Greedy-Algorithmus: Bei jedem Schritt wird eine lokal optimale Lösung ausgewählt, und am Ende erhält man eine global optimale Lösung. In unserem Fall ist die beste Option der teuerste Artikel. Aber ist das die beste Lösung? Glauben Sie nicht, dass es möglich ist, unsere Lösung ein wenig zu verbessern, um unseren Rucksack mit Artikeln zu füllen, die einen noch größeren Gesamtwert haben? Werfen wir einen Blick darauf, wie dies bewerkstelligt werden kann.
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
Hier berechnen wir zunächst das Wert-Gewichts-Verhältnis für jeden Artikel. Dies sagt uns den Wert jeder Einheit eines bestimmten Artikels. Und dann verwenden wir diese Verhältnisse, um unsere Artikel zu sortieren und in unsere Tasche zu legen. Lassen Sie uns Folgendes ausführen:
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
Wir erhalten diese Konsolenausgabe:
Das Gewicht des Rucksacks beträgt 29. Die Gesamtkosten der Gegenstände im Rucksack betragen 4150
Ein bisschen besser, nicht wahr? Der Greedy-Algorithmus trifft bei jedem Schritt eine lokal optimale Wahl und hofft, dass die endgültige Lösung ebenfalls optimal ist. Diese Annahme ist nicht immer gültig, aber für viele Aufgaben liefern Greedy-Algorithmen tatsächlich eine optimale Endlösung. Die zeitliche Komplexität dieses Algorithmus beträgt O(N). Ziemlich gut, oder?
Und da Sie auf dieser Website sind, gehe ich mal davon aus, dass Sie in Java schreiben. Aus diesem Grund empfehle ich Ihnen heute, sich mit einigen grundlegenden Algorithmen und konkreten Beispielen für deren Implementierung in Java vertraut zu machen. Mit „einige“ meine ich:
GO TO FULL VERSION