Quels sont les algorithmes de tri stables ?

Les algorithmes de tri stables incluent : 1. Tri par bulles ; 2. Tri par sélection ; 3. Tri par insertion ; 5. Tri par fusion ; 7. Tri par colline (shell) ;

L'environnement d'exploitation de ce tutoriel : système Windows 10, ordinateur Dell G3.

Analysez la stabilité des algorithmes de tri courants et donnez des raisons simples pour chacun.

Algorithme de tri stable :

1. Tri à bulles

Le tri à bulles consiste à déplacer les petits éléments vers l'avant ou les grands éléments vers l'arrière. La comparaison est une comparaison de deux éléments adjacents, et un échange se produit également entre ces deux éléments. Donc, si deux éléments sont égaux, je ne pense pas que vous les échangeriez de manière ennuyeuse.

Si deux éléments égaux ne sont pas adjacents, alors même si les deux sont adjacents lors de l'échange par paire précédent, ils ne seront pas échangés à ce moment-là, donc l'ordre des mêmes éléments n'a pas changé, donc le tri des bulles est une stabilité. algorithme de tri.

2. Tri par sélection

Le tri par sélection sélectionne le plus petit élément actuel pour chaque position, sélectionnez le plus petit pour la première position, sélectionnez le deuxième plus petit pour le deuxième élément parmi les éléments restants, et ainsi de suite. jusqu'à l'élément n-1, le n-ième élément n'a pas besoin d'être sélectionné, car c'est le seul plus grand élément restant. Ensuite, dans une sélection, si l'élément courant est plus petit qu'un élément, et que le petit élément apparaît après un élément égal à l'élément courant, alors la stabilité sera détruite après l'échange. n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

3、插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

4、快速排序

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j]>a[center_index]。

如果i和j都走不动了，i<=j，交换a[i]和a[j]，重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

5、归并排序

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2

C'est un peu difficile à prononcer. Par exemple, dans la séquence 5 8 5 2 9, on sait que sélectionner le 1ème élément 5 > dans la première passe correspondra Si 2 est échangé, l'ordre relatif de 2 et 5 dans la séquence d'origine sera détruit, donc la sélection le tri n'est pas un algorithme de tri stable.

3. Tri par insertion

Le tri par insertion insère un élément à la fois en fonction d'une petite séquence déjà ordonnée. Bien entendu, au début, cette petite séquence ordonnée ne comportait qu’un seul élément, qui était le premier élément. La comparaison commence à la fin de la séquence ordonnée, c'est-à-dire que l'élément que vous souhaitez insérer est comparé au plus grand déjà trié. S'il est plus grand que lui, insérez-le directement derrière lui, sinon continuez à regarder vers l'avant jusqu'à ce que vous ayez terminé. trouver l'élément dans lequel il doit être inséré.

Si vous rencontrez un élément égal à l'élément inséré, alors l'élément inséré placera l'élément que vous souhaitez insérer après l'élément égal.

Ainsi, l'ordre des éléments égaux n'a pas changé. L'ordre de la séquence non ordonnée d'origine est l'ordre après le tri, donc le tri par insertion est stable.

🎜4. Tri rapide🎜🎜🎜Le tri rapide a deux directions. L'indice i à gauche va jusqu'à la droite. Lorsque a[i] <= a[center_index], où center_index est l'index du tableau de l'élément central, qui est généralement considéré comme l'élément 0 du tableau. L'indice j à droite va jusqu'à la gauche, lorsque a[j]>a[center_index]. 🎜🎜Si i et j ne peuvent pas marcher, i<=j, échangez a[i] et a[j], répétez Le processus ci-dessus se poursuit jusqu'à i>j. Échangez a[j] et a[center_index] pour effectuer un tri rapide. Lorsque l'élément pivot est échangé avec a[j], il est très probable que la stabilité de l'élément précédent soit perturbée. Par exemple, la séquence est 5 3 3 4 3 8 9. 10 11, maintenant les éléments hub 5 et 3 (l'élément 5, l'indice commence à partir de 1 code>) sont échangés Cela perturbera la stabilité de l'élément 3, le tri rapide est donc un algorithme de tri instable. L'instabilité se produit au moment où l'élément central et a[j] sont échangés. 🎜🎜🎜5. Tri par fusion🎜🎜🎜Le tri par fusion consiste à diviser la séquence de manière récursive en séquences courtes. La sortie récursive est que la séquence courte n'a que des éléments <code>1 (considérés comme étant directement ordonnés) ou <. code>2 code> séquences (comparaison et échange 1), puis fusionnez chaque séquence de segments ordonnés en une longue séquence ordonnée, et continuez la fusion jusqu'à ce que les séquences d'origine soient toutes triées. On constate que lorsqu'il y a des éléments 1 ou 2, les éléments 1 ne seront pas échangés, et 2 les éléments ne seront pas échangés si les tailles sont égales et que personne ne les échange intentionnellement, cela ne rompt pas la stabilité. 🎜🎜Donc, lors du processus de fusion de courtes séquences ordonnées, la stabilité est-elle détruite ? 🎜🎜Non, lors du processus de fusion nous pouvons garantir que si les deux éléments courants sont égaux, nous sauvegarderons l'élément de la séquence précédente devant la séquence résultat, assurant ainsi la stabilité. Par conséquent, le tri par fusion est également un algorithme de tri stable. 🎜🎜🎜6. Le tri Radix🎜🎜🎜Le tri Radix consiste à trier d'abord par ordre faible, puis à collecter 🎜🎜puis à trier par ordre élevé, puis à collecter ;

Et ainsi de suite, jusqu'à la position la plus élevée. Parfois, certains attributs ont un ordre de priorité. Ils sont d'abord triés par priorité faible, puis par priorité élevée. L'ordre final est que ceux ayant une priorité élevée viennent en premier, et ceux ayant la même priorité élevée et faible viennent en premier. Le tri Radix est basé sur un tri séparé et une collecte séparée, il s'agit donc d'un algorithme de tri stable.

7. Tri en colline (coque)

Le tri en colline consiste à insérer et trier des éléments selon différentes longueurs de pas Lorsque les éléments sont très désordonnés au début, la taille du pas est la plus grande, donc le nombre d'éléments dans. le tri par insertion est très important, très rapide.

Lorsque les éléments sont essentiellement ordonnés et que la taille du pas est petite, le tri par insertion est très efficace pour les séquences ordonnées. Par conséquent, la complexité temporelle du tri Hill sera meilleure que O(n^2). En raison de plusieurs tris par insertion, nous savons qu'un tri par insertion est stable et ne modifiera pas l'ordre relatif des mêmes éléments. Cependant, dans différents processus de tri par insertion, les mêmes éléments peuvent se déplacer dans leurs tris par insertion respectifs, et finalement leur stabilité le sera. les changements sont brouillés, donc le tri des shells est instable. O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

8、堆排序

我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2-1， n/2-2，...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1

8. Tri par tas

Nous savons que la structure du tas est que les enfants du nœud i sont 2 * i et 2 * i + 1 nœud, un grand tas supérieur nécessite que le nœud parent soit supérieur ou égal à ses nœuds enfants 2, et un petit tas supérieur nécessite que le nœud parent soit inférieur ou égal à ses nœuds enfants 2. Dans une séquence de longueur n, le processus de tri des tas consiste à sélectionner la plus grande valeur à partir de n / 2 et ses nœuds enfants au total 3 (Grand tas supérieur) ou le plus petit (petit tas supérieur), le choix entre ces 3 éléments ne détruira certainement pas la stabilité. Mais lors de la sélection d'éléments pour les nœuds parents n/2-1, n/2-2, ...1, cela détruira la stabilité . Il est possible que le n/2ème nœud parent échange l'élément suivant, alors que le n/2-1ème nœud parent n'échange pas l'élément identique suivant, alors. la stabilité entre ces deux éléments identiques est détruite. Par conséquent, le tri par tas n’est pas un algorithme de tri stable. 🎜🎜Pour plus de connaissances connexes, veuillez visiter la rubrique 🎜FAQ🎜 ! 🎜

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!