Comment implémenter le tri par insertion et le tri Hill dans la structure de données Java

1. Texte

1. Le concept de tri et son application

1.1 Le concept de tri

Tri : Le soi-disant tri consiste à faire une chaîne d'enregistrements selon un ou certaines touches L'opération consistant à organiser la taille des mots par ordre croissant ou décroissant.

Stabilité : Supposons qu'il existe plusieurs enregistrements avec le même mot-clé dans la séquence d'enregistrements à trier. S'il est trié, l'ordre relatif de ces enregistrements reste inchangé, c'est-à-dire que dans la séquence d'origine, r[i]= r. [j], et r[i] est avant r[j], et dans la séquence triée, r[i] est toujours avant r[j], alors cet algorithme de tri est dit stable sinon il est appelé Instable ;

Tri interne : Tri dans lequel tous les éléments de données sont placés en mémoire.

Tri externe : Il y a trop d'éléments de données qui ne peuvent pas être placés dans la mémoire en même temps. Selon les exigences du processus de tri, les données ne peuvent pas être déplacées entre la mémoire interne et externe.

1.2 Application de tri

Après avoir lu les concepts de base du tri, certains amis peuvent se demander, même si j'apprends le tri, est-ce que cela sera utile dans la vraie vie ? En fait, le tri est partout dans la vie, comme le choix des différentes dimensions d'un produit, ou le classement des collèges et universités. En fait, il y a l'idée de trier derrière Apprendre à trier. peut nous aider à l'utiliser d'une autre manière pour observer tous les aspects de la vie et nous aider à mieux résoudre les problèmes de la vie.

1.3 Algorithmes de tri courants

Dans le domaine de la structure des données, nous avons quatre algorithmes de tri courants :

①Tri par insertion : tri par insertion directe, tri Hill

② Sélection trier : Tri par sélection, tri par tas

③Tri par échange : Tri à bulles, tri rapide

④Tri par fusion : Tri par fusion

2. Implémentation de l'algorithme de tri par insertion

En raison de la longueur de la relation, dans cet article. nous introduisons principalement le tri par insertion directe et le Tri par colline dans le tri par insertion, et le tri par insertion directe est souvent appelé tri par insertion.

2.1 Tri par insertion

2.1.1 Idée de base

Le tri par insertion directe est une méthode de tri par insertion simple

L'idée de base est d'insérer les enregistrements à trier un par un en fonction de la taille de leurs valeurs clés Dans la séquence ordonnée qui a été triée, jusqu'à ce que tous les enregistrements soient insérés, une nouvelle séquence ordonnée est obtenue

     En fait, lorsque nous jouons au poker, nous utilisons l'idée du tri par insertion. Lorsquevous piochez une nouvelle carte, vous la comparerez naturellement une par une avec la pile de cartes existante dans votre main et la placerez à l'endroit où elle devrait être après la comparaison. Nous ne savons donc peut-être pas ce qu'est le tri par insertion, mais notre approche subconsciente est exactement conforme au tri par insertion.

2.1.2 Tri par insertion directe

Utilisez un langage plus écrit pour décrire le tri par insertion directe : lors de l'insertion de l'élément i (i>=1), le tableau précédent[0], tableau[1],&hellip ;, array[i-1] a été trié. À ce stade, utilisez le code de tri de array[i] pour comparer l'ordre des codes de tri de array[i-1], array[i-2],... à trouvez la position d'insertion. C'est-à-dire que le tableau[i] est inséré et l'ordre des éléments à la position d'origine est déplacé vers l'arrière

Mais certains amis peuvent ne pas le comprendre, alors disons-le en termes simples. Maintenant

il y a un tableau désordonné devant vous, notre but est d'ajuster ce tableau désordonné par ordre croissant ou décroissant .

          En prenant l'ordre croissant comme exemple, puisque le tableau n'est pas ordonné, nous devons

commencer le tri à partir du deuxième élément du tableau. Pourquoi pas le premier ? Parce que lorsqu’il n’y a qu’un seul nombre, on ne peut pas le comparer avec d’autres éléments. Naturellement, le désordre n’existe pas. Par conséquent, lorsqu’il n’y a qu’un seul élément, on le classe par défaut.

Après avoir compris pourquoi nous devons trier à partir du deuxième élément, nous devons maintenant insérer et trier les éléments dans l'ordre. La première est l'insertion et le tri du deuxième élément. Dans l'image ci-dessous, nous constaterons que le deuxième élément est 44. 44 est supérieur au premier élément de 3, il n'est donc pas nécessaire de déplacer le deuxième élément. Vient ensuite l'insertion et le tri du troisième élément. Nous avons constaté que le troisième élément 38 est plus petit que le deuxième élément 44, ce qui ne répond pas à nos attentes en termes d'ordre croissant, nous déplaçons donc 44 à la position 38. Entre le deuxième et le deuxième élément. troisièmes éléments, Après tri, nous avons constaté que 38 est supérieur à 3, c'est-à-dire que les premier et deuxième éléments sont également dans l'ordre, il n'est donc pas nécessaire de déplacer la position du premier élément. Pour le moment, nous l'avons confirmé. 38 doit être dans le deuxième élément de l'élément du tableau, nous insérons donc simplement 38 à la position du deuxième élément. Je pense que l'insertion et le tri des éléments suivants ici devraient se faire manuellement. La prochaine étape est l'écriture du code. En termes de code, comment pouvons-nous implémenter l'insertion et le tri des éléments ci-dessus ? Nous avons pris deux variables principales

"des"

et "end" est l'index initial de l'élément que nous voulons insérer, et end représente l'index du dernier élément de la séquence avant l'insertion. des, end continuera d'avancer, donc quand le mouvement de end s'arrêtera-t-il, c'est-à-dire la fin de la comparaison, qui peut être grossièrement divisée en deux situations : ① L'élément représenté par des est plus grand que l'élément représenté par end L'élément ②end a atteint le premier élément de la séquence. À ce moment, des est soit le premier élément, soit le deuxième élément. ?                                   . Complexité temporelle : O(N^2)③ Complexité spatiale : O(1), c'est un algorithme de tri stable④ Stabilité : stable

2.1.3 Tri par colline (réduire le tri par incrément)

La méthode de tri par colline est également appelée méthode d'incrémentation décroissante.

L'idée de base de la méthode de tri Hill est la suivante : sélectionnez d'abord un nombre entier, divisez tous les enregistrements du fichier à trier en groupes entiers, placez tous les enregistrements avec une distance de dans le même groupe et triez les enregistrements dans chaque groupe. Répétez ensuite le travail de regroupement et de tri ci-dessus. Lorsque l'entier est égal à 1, tous les enregistrements sont triés dans le même groupe. #                                                                                        notre à trier

Ainsi, lorsque certains amis voient cela, ils peuvent se demander pourquoi plusieurs tris par insertion sont effectués. Quelle est la différence entre le tri par insertion unique et le tri par insertion normal ? Ne vous inquiétez pas, nous y répondrons une par une ci-dessous. ?                                                                                                                                                         . Par conséquent, le but du tri Hill, à l'exception du fait que le dernier tri est un tri par insertion normal, est d'ajuster en permanence l'ensemble des éléments afin qu'il soit constamment proche de l'ordre.尔 Ensuite, la différence entre le tri de Hill, à l'exception de la dernière insertion et du tri et du tri par insertion normal. Grâce à l'étude ci-dessus du tri par insertion, nous constaterons que pour un tableau désordonné, si un élément veut atteindre la bonne position, il doit être comparé aux autres éléments un par un, c'est-à-dire déplacé pas à pas. Cela est acceptable lorsque le nombre d'éléments dans le tableau est petit, mais lorsque le nombre d'éléments dans le tableau est grand, par ordre croissant, imaginez que le plus grand élément du tableau est situé à la première position du tableau, alors est Il est nécessaire de Cet élément ne peut atteindre la dernière position du tableau qu'après l'avoir comparé un par un avec les autres éléments du tableau. Mais lorsque l'on augmente le rythme de comparaison, c'est-à-dire que l'on augmente la distance entre les deux éléments comparés, alors. cet élément est Sinon, vous pouvez arriver plus rapidement là où il devrait être

. Dans le cas d'échecs volants, le tri par insertion renvoie 1 à chaque fois et le tri par hachage, sauf que le dernier tri par insertion renvoie un point de 1, le reste du tri par insertion est tous supérieur à 1. , il est donc concevable que le tri par hachage peut arriver plus rapidement à la fin du tri.

Afin de faciliter la compréhension des amis, cette partie du code est divisée en deux parties : ① tri par insertion directe à pas fixe ② tri par hachage.

        先是固定步伐的直接插入排序，先让我们通过图片来直观的看到数组数组内的元素通过这种操作后的变化。 

//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}

         接着就是希尔排序

         上述的代码是gap=3的情况下的直接插入排序，那么对于希尔排序而言，我们该对gap该如何选择呢？对于不同gap值的插入排序来说，我们会发现：gap越大，元素跳得越快，数组越不接近有序；而gap越小，元素跳的越慢，数组越接近有序。由于数组的大小不定，因此希尔排序也没有一个合适gap值适用于所有数组，显然，这个gap值一定是动态变化的。

        对于gap的动态变化，常见的有两种：

①令gap等于数组的元素个数，每次插入排序后令gap除等2

②另一种则是令gap等于数组的元素个数，不过每次插入排序后令gap除以3再加1

        无论哪种处理都能使gap动态变化并最后等于1，对数组进行一次插入排序，达到最后想要的效果。

        代码如下：

//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}

二、测试代码

        为了方便小伙伴们测试排序后的效果，为大家提供了测试的代码并包含排序的具体代码和包含的头文件。

#include 
#include 
#include 
 
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}
 
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}
 
 
//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}
 
//打印排序好的数组
void PrintSort(int*arr,int n)
{
	for(int i=0;i
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!