Algorithme de tri simple

Le secteur informatique d'aujourd'hui n'est plus aussi compliqué qu'avant. Il y a trop d'employés, ce qui entraîne un surplus de programmeurs juniors, ce qui a également indirectement conduit à un seuil de recrutement de plus en plus élevé, obligeant les programmeurs à maîtriser davantage. et plus de connaissances.

Les algorithmes sont aussi un sujet qui fait débat depuis longtemps. Les programmeurs doivent-ils maîtriser les algorithmes ? Différentes personnes ont des réponses différentes. En fait, de nombreuses entreprises ont certaines exigences en matière d'algorithmes. Certaines entreprises exigent directement que les intervieweurs rédigent à la main les questions relatives aux algorithmes lors des entretiens. Cela met à rude épreuve les exigences techniques des programmeurs. Par conséquent, face à l’environnement actuel, nous devons maîtriser l’algorithme afin d’occuper une place dans les travaux futurs.

Ensuite, je présenterai brièvement plusieurs algorithmes de tri, j'espère que cela vous sera utile.

Bubble Sort

Bubble Sort est un algorithme de tri relativement simple.

Il visite à plusieurs reprises la colonne d'éléments à trier, compare tour à tour deux éléments adjacents et les échange si leur ordre (par exemple du grand au petit, première lettre de A à Z) est erroné. Le travail des éléments en visite est répété jusqu'à ce qu'aucun élément adjacent ne doive être échangé, ce qui signifie que la colonne d'éléments a été triée.

Le nom de cet algorithme vient du fait que les éléments plus gros « flotteront » lentement vers le haut de la séquence par échange (dans l'ordre croissant ou décroissant), tout comme les bulles de dioxyde de carbone dans les boissons gazeuses finiront par flotter vers le haut, d'où le nom "tri à bulles".

Démonstration :

Le code est le suivant :

@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 + "次");
}

Résultat d'exécution :

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

Sélection sort

Le tri par sélection est un algorithme de tri simple et intuitif. Son principe de fonctionnement est le suivant : sélectionnez d'abord l'élément le plus petit (ou le plus grand) parmi les éléments de données à trier, stockez-le au début de la séquence, puis recherchez l'élément le plus petit (le plus grand) parmi les éléments non triés restants et placez-le. à la fin de la séquence triée. Et ainsi de suite, jusqu'à ce que le nombre de tous les éléments de données à trier soit nul. Le tri par sélection est une méthode de tri instable.

Démonstration :

Le code est le suivant :

@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> Résultats d'exécution : </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

La mise en œuvre est également très simple, tout d'abord Une variable d'index est définie dans la boucle externe pour stocker la valeur de i. Ceci afin d'éviter les comparaisons répétées, car après chaque tour de comparaison, les i premiers éléments sont déjà triés, il n'est donc pas nécessaire de le faire. comparez à nouveau, commencez simplement par Commencez simplement i. Les comparaisons suivantes sont toutes basées sur l'élément à la position d'index. Si l'élément à la position d'index est la valeur minimale après la comparaison, il n'est pas nécessaire d'échanger, il suffit de ne pas bouger. Et si un élément plus petit que l'élément à l'index est trouvé, attribuez l'index de l'élément à index, puis continuez à comparer jusqu'à ce que la comparaison soit terminée. L'index obtenu une fois la comparaison terminée est la valeur minimale du tableau, alors à ce moment-là, il vous suffit d'échanger l'élément en position d'index avec l'élément en position i.

Tri par insertion

Le tri par insertion est un algorithme de tri simple, intuitif et stable. S'il existe une séquence de données déjà triée et qu'il est nécessaire d'insérer un nombre dans la séquence de données triée, mais que la séquence de données est toujours ordonnée après l'insertion, une nouvelle méthode de tri - l'insertion est requise. Le tri par insertion consiste à insérer une donnée dans les données ordonnées qui ont été triées, de manière à obtenir une nouvelle donnée ordonnée avec le nombre plus un. L'algorithme est adapté au tri d'une petite quantité de données. La complexité temporelle est O (n). ^2). C'est une méthode de tri stable. L'algorithme d'insertion divise le tableau à trier en deux parties : la première partie contient tous les éléments du tableau, sauf le dernier élément (ce qui fait au tableau un espace de plus pour avoir une position d'insertion), et la deuxième partie ne contient que celui-ci. élément (c'est-à-dire l'élément à insérer). Une fois la première partie triée, ce dernier élément est inséré dans la première partie triée.

L'idée de base du tri par insertion est la suivante : à chaque étape, un enregistrement à trier est inséré à la position appropriée dans le tableau précédemment trié en fonction de la taille de sa valeur clé, jusqu'à ce que tous soient insérés.

Démonstration :

Le code est le suivant :

@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>Résultat d'exécution : </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Alors voilà, parce que les éléments du tableau Nous n'en sommes pas sûrs, nous ne pouvons donc considérer le premier élément du tableau que comme une séquence ordonnée, donc à partir du deuxième élément du tableau est l'élément dont nous avons besoin pour trouver la position d'insertion. Ainsi, la boucle externe commence à partir de 1, puis enregistre arr[i], qui est le deuxième élément actuel, puis trouve l'indice d'élément précédent de l'élément à insérer, qui est i-1 à ce moment, pendant un certain temps. Boucle pour comparer.

Lorsque insertIndex est inférieur à 0, vous devez quitter la boucle car elle a été comparée à tous les éléments précédents. Lors du processus de comparaison, si l'élément à insérer est plus petit que l'élément précédent, l'élément précédent est déplacé vers l'arrière, c'est-à-dire que la valeur de l'élément précédent est directement affectée à la position de l'élément à insérer. L'élément à insérer ayant été enregistré au départ, il vous suffit d'attribuer la valeur de l'élément à insérer à son élément précédent. Étant donné que insertIndex effectue une opération de décrémentation dans la boucle while, son indice d'élément précédent doit être insertIndex + 1. Et si la valeur de l'élément à insérer est supérieure à l'élément précédent, alors il n'entrera pas dans la boucle while, de sorte que la position après insertIndex + 1 est toujours sa propre position, donc la valeur ne change pas après l'affectation, et ainsi de suite pour les opérations ultérieures.

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!