Einfacher Sortieralgorithmus

Die aktuelle IT-Branche ist nicht mehr so ​​einfach zu handhaben wie früher. Es gibt zu viele Mitarbeiter, was zu einem Überschuss an Nachwuchsprogrammierern führt. Dies hat indirekt auch dazu geführt, dass die Rekrutierungsschwelle des Unternehmens immer höher wird Programmierer beherrschen immer mehr Wissen.

Algorithmen sind auch ein Thema, über das schon lange diskutiert wird. Sollten Programmierer Algorithmen beherrschen? Unterschiedliche Personen haben unterschiedliche Antworten. Tatsächlich stellen viele Unternehmen bestimmte Anforderungen an Algorithmen. Einige Unternehmen verlangen direkt, dass Interviewer Algorithmenfragen handschriftlich verfassen. Dies stellt die technischen Anforderungen der Programmierer auf eine große Probe. Daher müssen wir angesichts der heutigen Umgebung den Algorithmus beherrschen, um in der zukünftigen Arbeit einen Platz einzunehmen.

Als nächstes werde ich einige Sortieralgorithmen kurz vorstellen, ich hoffe, dass es Ihnen hilfreich sein wird.

Bubble Sort

Bubble Sort ist ein relativ einfacher Sortieralgorithmus.

Es besucht wiederholt die Spalte der zu sortierenden Elemente, vergleicht nacheinander zwei benachbarte Elemente und vertauscht sie, wenn ihre Reihenfolge (z. B. von groß nach klein, Anfangsbuchstabe von A bis Z) falsch ist. Die Arbeit des Besuchs von Elementen wird wiederholt, bis keine benachbarten Elemente mehr ausgetauscht werden müssen, was bedeutet, dass die Elementspalte sortiert wurde.

Der Name dieses Algorithmus rührt von der Tatsache her, dass größere Elemente durch Austausch (in aufsteigender oder absteigender Reihenfolge) langsam an die Spitze der Sequenz „schweben“, genau wie es schließlich die Kohlendioxidblasen in kohlensäurehaltigen Getränken tun werden nach oben schweben, daher der Name „Blasensortierung“.

Demonstration:

Der Code lautet wie folgt:

@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 统计比较次数
	int count = 0;
	// 第一轮比较
	for (int i = 0; i  arr[j + 1]) {
				// 交换位置
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			count++;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("一共比较了:" + count + "次");
}

Laufergebnis:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比较了:105次

Auswahl Sortieren

Selection Sort ist ein einfacher und intuitiver Sortieralgorithmus. Sein Arbeitsprinzip besteht darin, zuerst das kleinste (oder größte) Element aus den zu sortierenden Datenelementen auszuwählen, es am Anfang der Sequenz zu speichern und dann das kleinste (größte) Element aus den verbleibenden unsortierten Elementen zu finden und zu platzieren am Ende der sortierten Sequenz. Und so weiter, bis die Anzahl aller zu sortierenden Datenelemente Null ist. Die Auswahlsortierung ist eine instabile Sortiermethode.

Demonstration:

Der Code lautet wie folgt:

@Test
public void SelectionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 0; i <p>Laufende Ergebnisse: </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Die Implementierung ist ebenfalls Sehr einfach: Zunächst wird in der äußeren Schleife eine Indexvariable definiert, um den Wert von i zu speichern. Dies dient dazu, wiederholte Vergleiche zu vermeiden, da nach jeder Vergleichsrunde die ersten i-Elemente bereits sortiert sind, sodass dies nicht erforderlich ist Vergleichen Sie noch einmal, beginnen Sie einfach mit Just start i. Die nachfolgenden Vergleiche basieren alle auf dem Element an der Indexposition. Wenn das Element an der Indexposition nach dem Vergleich den Mindestwert aufweist, ist kein Austausch erforderlich, sondern nur keine Verschiebung. Wenn ein Element gefunden wird, das kleiner als das Element am Index ist, weisen Sie den Index des Elements dem Index zu und fahren Sie dann mit dem Vergleich fort, bis der Vergleich abgeschlossen ist. Der nach Abschluss des Vergleichs erhaltene Index ist der Mindestwert im Array. Dann tauschen Sie zu diesem Zeitpunkt einfach das Element an der Indexposition mit dem Element an Position i aus.

Einfügungssortierung

Einfügungssortierung ist ein einfacher, intuitiver und stabiler Sortieralgorithmus. Wenn eine bereits sortierte Datensequenz vorhanden ist und eine Zahl in die sortierte Datensequenz eingefügt werden muss, die Datensequenz nach dem Einfügen jedoch immer noch geordnet ist, ist eine neue Sortiermethode – Einfügung – erforderlich Bei der Einfügungssortierung werden Daten in die sortierten geordneten Daten eingefügt, um neue geordnete Daten mit der Zahl plus eins zu erhalten. Der Algorithmus eignet sich zum Sortieren einer kleinen Datenmenge. Die Zeitkomplexität beträgt O(n). ^2). Es handelt sich um eine stabile Sortiermethode. Der Einfügealgorithmus teilt das zu sortierende Array in zwei Teile: Der erste Teil enthält alle Elemente des Arrays mit Ausnahme des letzten Elements (wodurch das Array um einen weiteren Platz für eine Einfügeposition erweitert wird), und der zweite Teil enthält nur dieses ein Element (d. h. das einzufügende Element). Nachdem der erste Teil sortiert ist, wird dieses letzte Element in den sortierten ersten Teil eingefügt.

Die Grundidee der Einfügesortierung besteht darin, dass bei jedem Schritt ein zu sortierender Datensatz entsprechend der Größe seines Schlüsselwerts an der entsprechenden Position im zuvor sortierten Array eingefügt wird, bis alle eingefügt sind.

Demonstration:

Der Code lautet wie folgt:

@Test
public void InsertionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 1; i = 0 && insertValue <p>Laufendes Ergebnis: </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Also hier, weil Wir sind uns der Array-Elemente nicht sicher, daher können wir nur das erste Element des Arrays als geordnete Sequenz betrachten. Ausgehend vom zweiten Element des Arrays müssen wir also die Einfügeposition finden. Die äußere Schleife beginnt also bei 1 und speichert dann arr[i], das aktuelle zweite Element, und findet dann den vorherigen Elementindex des einzufügenden Elements, das zu diesem Zeitpunkt i-1 ist Schleife zum Vergleichen.

Wenn insertIndex kleiner als 0 ist, sollten Sie die Schleife verlassen, da sie mit allen vorherigen Elementen verglichen wurde. Wenn während des Vergleichsvorgangs das einzufügende Element kleiner als das vorherige Element ist, wird das vorherige Element nach hinten verschoben, dh der Wert des vorherigen Elements wird direkt der Position des einzufügenden Elements zugewiesen. Da das einzufügende Element zu Beginn gespeichert wurde, müssen Sie nur den Wert des einzufügenden Elements seinem vorherigen Element zuweisen. Da insertIndex in der while-Schleife eine Selbstdekrementierungsoperation ausführt, sollte sein vorheriger Elementindex insertIndex + 1 sein. Und wenn der Wert des einzufügenden Elements größer als der des vorherigen Elements ist, gelangt es nicht in die while-Schleife, sodass die Position nach insertIndex + 1 immer noch seine eigene Position ist und sich der Wert nach der Zuweisung nicht ändert. und so weiter für nachfolgende Operationen.

Das obige ist der detaillierte Inhalt vonEinfacher Sortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!