Implémenter le tri par insertion à l'aide du code Java et du pseudocode

Introduction au tri par insertion :

Je crois que la plupart des gens ont joué au poker. Beaucoup de gens aiment prendre une carte en main lorsqu'on leur distribue une carte et la commander. dans l'ordre. Venez déposer vos cartes. On part avec une main gauche vide et les cartes sont sur la table. Nous prenons ensuite une carte à la fois sur la table et l'insérons à sa place dans la main gauche. Pour trouver la bonne position d'une carte, nous la comparons avec toutes les cartes déjà en main de droite à gauche.

Tutoriels vidéo gratuits liés à Java recommandés : Tutoriels vidéo gratuits sur Java

Pseudo code :

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

code java :

//升序排序
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;
		}
}

Jetons un coup d'œil aux étapes de fonctionnement du tri par insertion

Utilisons le tableau A[2,4,7,1,3,6] comme exemple

Chaque Dans la boucle for, le rectangle jaune est la valeur de A[j]. Dans la boucle while de la ligne 7, il est comparé à la valeur du rectangle bleu à gauche. La flèche bleue indique que le tableau est déplacé d'une position vers la droite sur la ligne 8 et la flèche jaune indique où le mot-clé est déplacé sur la ligne 11.

Le premier cycle : comme indiqué ci-dessous :

Le deuxième cycle : comme indiqué ci-dessous :

Remarque : Ici, A[2] est supérieur à A[1], car A[1] est définitivement supérieur à A[0], il n'est donc pas nécessaire de comparer A[2] avec A[1] taille. La boucle while se terminera car la condition n'est pas remplie.

Le troisième cycle : comme le montre l'image ci-dessous :

Le quatrième cycle : comme le montre l'image ci-dessous :

La cinquième boucle : comme indiqué ci-dessous :

Le tableau A est maintenant comme indiqué sur la figure :

Dans la sixième boucle, j vaut 6, ce qui ne satisfait pas la condition de boucle j

Articles et tutoriels recommandés sur Java : Programme d'entrée Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!