Implementieren Sie die Einfügungssortierung mithilfe von Java-Code und Pseudocode

Einführung in die Einfügungssortierung:

Ich glaube, die meisten Leute haben Poker gespielt. Viele Leute nehmen gerne eine Karte auf die Hand, wenn ihnen eine Karte ausgeteilt wird Kommen Sie und legen Sie Ihre Karten ab. Wir beginnen mit einer leeren linken Hand und die Karten liegen auf dem Tisch. Anschließend nehmen wir jeweils eine Karte vom Tisch und stecken sie an ihren Platz in der linken Hand. Um die richtige Position einer Karte zu finden, vergleichen wir sie von rechts nach links mit jeder bereits in der Hand befindlichen Karte.

Empfohlene kostenlose Java-Video-Tutorials: Kostenlose Java-Video-Tutorials

Pseudocode:

INSERTION-SORT(A)	//A是数组
 for j = 2 to A.length
key = A[j]
//(将A[j]插入排序序列A[1..j-1])
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key

Java-Code:

//升序排序
public void InsertSortAscending(int[] A){
		for(int j = 1;j < A.length;j++){
			int key = A[j];
			//将A[j]插入排序序列A[1..j-1]
			int i = j - 1;
			while(i >= 0 && A[i] > key){
				A[j+1] = A[i];
				i = i - 1;
			}
			A[i+1] = key;
		}
}

Werfen wir einen Blick auf die Arbeitsschritte der Einfügesortierung

Verwenden Sie Array A[2,4,7,1,3,6] als Beispiel

In der for-Schleife ist das gelbe Rechteck der Wert von A[j]. In der while-Schleife in Zeile 7 wird es mit dem Wert des blauen Rechtecks ​​auf der linken Seite verglichen. Der blaue Pfeil zeigt an, dass das Array in Zeile 8 um eine Position nach rechts verschoben wurde, und der gelbe Pfeil zeigt an, wohin das Schlüsselwort in Zeile 11 verschoben wurde.

Der erste Zyklus: wie im Bild unten gezeigt:

Der zweite Zyklus: wie im Bild unten gezeigt:

Hinweis: Hier ist A[2] größer als A[1], da A[1] definitiv größer als A[0] ist, sodass kein Vergleich von A[2 erforderlich ist ] mit der Größe A[1]. Die while-Schleife wird beendet, da die Bedingung nicht erfüllt ist.

Der dritte Zyklus: wie im Bild unten gezeigt:

Der vierte Zyklus: wie im Bild unten gezeigt:

Die fünfte Schleife: wie in der Abbildung unten gezeigt:

Das A-Array sieht nun wie in der Abbildung gezeigt aus:

In der sechsten Schleife ist j 6, was die Schleifenbedingung j

Empfohlene Java-bezogene Artikel und Tutorials: Java-Einstiegsprogramm

Das obige ist der detaillierte Inhalt vonImplementieren Sie die Einfügungssortierung mithilfe von Java-Code und Pseudocode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!