L'algorithme de tri est utilisé dans de nombreux endroits. J'ai récemment revu l'algorithme et je l'ai simplement implémenté moi-même. Je vais l'enregistrer ici et sauvegarder du matériel pour une révision future.
Sans plus attendre, examinons un à un les algorithmes de tri classiques :
1. Sélectionnez le tri
L'idée de base du tri par sélection est que pendant le processus de parcours du tableau, si i représente le numéro de séquence actuel qui doit être trié, vous devez trouver la valeur minimale parmi les [i...n-1] restants. , puis pointez la valeur minimale trouvée sur i les valeurs sont échangées. Étant donné que chaque processus de détermination des éléments aura un sous-processus de sélection de la valeur maximale, les gens appellent cela le tri par sélection. Prenons un exemple :
Initiale : [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
je = 0 : [2, 17, 16, 16, 7, 31, 39, 32, 38, 11] (0e [38]<->8e [2])
je = 1 : [2, 7, 16, 16, 17, 31, 39, 32, 38, 11] (1er [38]<->4e [17])
je = 2 : [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (2e [11]<->9e [16])
i = 3 : [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (aucun échange requis)
je = 4 : [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4e [17]<->9e [16])
je = 5 : [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5e [31]<->9e [17])
je = 6 : [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6e [39]<->9e [31])
i = 7 : [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (aucun échange requis)
i = 8 : [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (aucun échange requis)
i = 9 : [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (aucun échange requis)
Comme le montre l'exemple, à mesure que le tri par sélection progresse (i augmente progressivement), le nombre de comparaisons deviendra de moins en moins important. Cependant, que le tableau soit initialement ordonné ou non, le tri par sélection effectuera une comparaison de sélection. de i à la fin du tableau. Ainsi, pour un tableau de longueur donnée, le nombre de comparaisons dans le tri par sélection est fixe : 1 + 2 + 3 + …. , et le nombre d'échanges est lié à l'ordre du tableau initial. Si l'ordre initial du tableau est aléatoire, alors dans le pire des cas, les éléments du tableau seront échangés n fois, et dans le meilleur des cas, cela peut être 0 fois (. le tableau lui-même est une séquence).
On peut en déduire que la complexité temporelle et la complexité spatiale du tri par sélection sont respectivement O(n2) et O(1) (le tri par sélection ne nécessite qu'un espace supplémentaire pour l'échange d'éléments de tableau).
Code d'implémentation :
Copiez le code comme suit :
/**
*Tri de sélection
*/
SÉLECTION(nouveau Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
pour (int je = 0; je < len; i++) {
int sélectionné = je;
pour (int j = i + 1; j < len; j++) {
int comparer = array[j].compareTo(array[selected]);
if (comparer != 0 && comparer < 0 == monter) {
sélectionné = j;
}
}
échange (tableau, i, sélectionné);
}
}
})
2. Tri par insertion
L'idée de base du tri par insertion est que pendant le processus de parcours du tableau, en supposant que les éléments avant le numéro de série i, c'est-à-dire [0..i-1], ont été triés, ce voyage doit trouver la position correcte. k de l'élément x correspondant à i, et Dans le processus de recherche de cette position k, les éléments comparés sont reculés d'une position un par un pour « faire de la place » à l'élément x Enfin, la valeur de l'élément correspondant à k est attribuée à. x. Le tri par insertion est également nommé en fonction des caractéristiques du tri.
Voici un exemple : Les nombres marqués en rouge sont des nombres insérés. Les nombres barrés sont des éléments qui ne participent pas à ce tri. Les éléments entre les nombres marqués en rouge et les nombres barrés sont des éléments qui sont décalés vers l'arrière. un par un, comme Les éléments participant au deuxième tri sont [11, 31, 12], et l'élément qui doit être inséré est 12, mais 12 n'est pas actuellement dans la bonne position, nous devons donc l'insérer avec les éléments précédents 31 et 11 en séquence. Comparez, déplacez les éléments comparés tout en comparant et arrêtez de comparer lorsque vous trouvez le premier élément 11 qui est inférieur à 12. A ce moment, l'index 1 correspondant à 31 est la position où 12 doit être inséré.
Initiale : [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
Premier passage : [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (aucun élément déplacé)
Deuxième voyage : [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 recule)
Troisième voyage : [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 reculent tous)
Quatrième passe : [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (aucun élément mobile)
Cinquième voyage : [5, 11, 12, 30, 31, 34, 26, 38, 36, 18] (31, 34 recule)
Le sixième voyage : [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31, 34 recule)
La septième passe : [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (aucun élément mobile)
Huitième voyage : [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 recule)
Neuvième voyage : [5, 11, 12, 18, 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 en reculant)
Le tri par insertion est meilleur que le tri par sélection car il peut tirer parti du fait que la première partie des éléments du tableau a été triée pendant le processus de tri, réduisant ainsi le nombre de comparaisons. Bien entendu, cet avantage dépend de l'ordre initial du tri. array. En fin de compte, dans le mauvais cas (le tableau donné se trouve être dans l'ordre inverse), le nombre de comparaisons et de déplacements requis pour le tri par insertion sera égal à 1 + 2 + 3... + n = n * (n + 1) / 2. Dans ce cas extrême, le tri par insertion L'efficacité du tri est encore pire que celle du tri par sélection. Par conséquent, le tri par insertion est une méthode de tri instable et l'efficacité de l'insertion est étroitement liée à l'ordre initial du tableau. En général, la complexité temporelle et la complexité spatiale du tri par insertion sont respectivement O(n2) et O(1).
Code d'implémentation :
Copiez le code comme suit :
/**
*Tri par insertion
*/
INSERTION(nouveau Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
pour (int je = 1; je < len; i++) {
T toInsert = tableau[i];
int j = je;
pour (; j > 0; j) {
int comparer = array[j - 1].compareTo(toInsert);
if (comparer == 0 || comparer < 0 == monter) {
casser;
}
tableau[j] = tableau[j - 1];
}
array[j] = toInsérer ;
}
}
})
3. Tri à bulles
Le tri à bulles peut être considéré comme l'algorithme de tri le plus classique. Je me souviens que cet algorithme a été le premier avec lequel j'ai été en contact lorsque j'étais à l'école. Parce que la méthode d'implémentation est la plus simple, il s'agit d'une boucle for à deux niveaux. la boucle interne, on juge si deux éléments adjacents sont dans l'ordre inverse. Si c'est le cas, échangez les deux éléments et effectuez une boucle externe pour "faire flotter" le plus petit élément parmi les éléments restants du tableau vers l'avant, c'est ce qu'on appelle. tri des bulles.
Donnons un exemple simple comme d'habitude :
État initial : [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
Le premier voyage de la couche interne : [24, 19, 26, 39, 36, 7, 31, 29, 23, 38] (9e [23]<->8e [38)
Deuxième passage de la couche interne : [24, 19, 26, 39, 36, 7, 31, 23, 29, 38] (8e [23]<->7e [29])
Le troisième passage de la couche interne : [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7e [23]<->6e [31])
Le quatrième passage de la couche interne : [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7 et 23 sont tous dans le bon ordre, aucun échange requis)
Le cinquième voyage de la couche interne : [24, 19, 26, 39, 7, 36, 23, 31, 29, 38] (5e [7]<->4e [36])
Le sixième voyage de la couche interne : [24, 19, 26, 7, 39, 36, 23, 31, 29, 38] (4e [7]<->3e [39])
La septième passe de la couche interne : [24, 19, 7, 26, 39, 36, 23, 31, 29, 38] (3e [7]<->2e [26])
La huitième passe de la couche interne : [24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (2e [7]<->1er [19])
Le neuvième voyage de la couche interne : [7, 24, 19, 26, 39, 36, 23, 31, 29, 38] (1er [7]<->0ème [24])
……….
En fait, le tri à bulles est similaire au tri par sélection. Le nombre de comparaisons est le même, n * (n + 1) / 2. Cependant, le tri à bulles effectuera des échanges supplémentaires dans le processus de sélection de la valeur minimale (le tri à bulles n'a besoin que de S'il s'avère que l'ordre des éléments adjacents n'est pas correct, il sera échangé. En conséquence, le tri par sélection ne décidera s'il faut échanger en fonction de la situation qu'une fois la comparaison de la boucle interne terminée), donc à mon avis, le tri par sélection appartient. au tri des bulles.
Code d'implémentation :
Copiez le code comme suit :
/**
* Tri à bulles, c'est très similaire au tri par insertion
*/
BULLE(nouveau Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int longueur = tableau.longueur;
int lastExchangedIdx = 0;
pour (int i = 0; i < longueur; i++) {
// marque le drapeau pour identifier si l'échange est faux
booléen isExchanged = faux ;
// la dernière comparaison et l'échange ont eu lieu avant d'atteindre l'index i
int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
pour (int j = longueur 1; j > currOrderedIdx; j) {
int comparer = array[j - 1].compareTo(array[j]);
if (comparer != 0 && comparer > 0 == monter) {
échange(tableau, j 1, j);
estExchanged = vrai ;
lastExchangedIdx = j;
}
}
// si aucun échange n'a lieu, cela signifie que le tableau est déjà en ordre
si (isExchanged == false) {
casser;
}
}
}
})
4. Tri en colline
Le tri Hill est né parce que le tri par insertion rencontrait le problème du déplacement de trop d'éléments lorsqu'il s'agissait de grands tableaux. L'idée du tri Hill est de "diviser et conquérir" un grand tableau en plusieurs petits tableaux, divisés par des espaces, comme le tableau [1, 2, 3, 4, 5, 6, 7, 8]. = 2 pour diviser, il peut être divisé en deux tableaux [1, 3, 5, 7] et [2, 4, 6, 8] (en conséquence, comme écart = 3 , alors les tableaux divisés sont : [1, 4, 7], [2, 5, 8], [3, 6]) Effectuez ensuite un tri par insertion sur les tableaux divisés, puis réduisez-les après le tri de chaque sous-tableau. Répétez les étapes précédentes jusqu'à ce que l'écart = 1 , c'est-à-dire que le tri par insertion est effectué sur l'ensemble du tableau à ce stade, le tableau est essentiellement trié, de sorte que les éléments qui doivent être déplacés seront très petits, ce qui résout le problème du nombre de déplacements supplémentaires dans le tri par insertion lors du traitement de grands éléments. tableaux d’échelle.
Veuillez vous référer au tri par insertion pour des exemples spécifiques.
Le tri Hill est une version améliorée du tri par insertion. Il est très utile pour améliorer l'efficacité lorsque la quantité de données est importante. Lorsque la quantité de données est faible, il est recommandé d'utiliser directement le tri par insertion.
Code d'implémentation :
Copiez le code comme suit :
/**
* Tri des coquilles
*/
SHELL(nouveau Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int longueur = tableau.longueur;
écart int = 1 ;
// utilise le plus proche de la longueur / 3 comme premier espace
while (espace < longueur / 3) {
écart = écart * 3 + 1 ;
}
tandis que (écart >= 1) {
pour (int i = écart; i < longueur; i++) {
T suivant = tableau[i];
int j = je;
tandis que (j >= écart) {
int comparer = array[j - gap].compareTo(next);
// trouve déjà sa position
if (comparer == 0 || comparer < 0 == monter) {
casser;
}
tableau[j] = tableau[j - écart];
j -= écart ;
}
si (j != je) {
tableau[j] = suivant;
}
}
écart /= 3 ;
}
}
})
5. Fusionner le tri
Le tri par fusion est implémenté par récursion, qui est une méthode « diviser pour régner ». Le tableau cible est divisé en deux à partir du milieu, puis les deux tableaux sont triés séparément. Une fois le tri terminé, les deux tableaux triés sont « fusionnés ». " dans Together, la chose la plus importante dans le tri par fusion est le processus de « fusion ». Le processus de fusion nécessite un espace supplémentaire cohérent avec la longueur des deux tableaux qui doivent être fusionnés. Par exemple, les tableaux qui doivent être spécifiés sont : [3, 6, 8, 11] et [1, 3, 12, 15] (Bien que logiquement divisés en deux tableaux, ces éléments sont en fait toujours dans le tableau d'origine, mais ils sont divisés en deux tableaux via certains index. Le tableau d'origine pour [3, 6, 8, 11, 1, 3, 12, 15, nous plaçons trois pointeurs lo, mid et high sur 0, 3 et 7 respectivement. Une division logique des sous-réseaux peut être réalisée.) Ensuite, la longueur du tableau supplémentaire requis est 4 + 4 = 8. Le processus de fusion peut être brièvement résumé comme suit :
1) Copiez les éléments des deux sous-tableaux dans le nouveau tableau copiéArray En prenant l'exemple mentionné ci-dessus comme exemple, copiéArray = [3, 6, 8, 11, 1, 3, 12, 15];
2) Définissez deux pointeurs pour qu'ils pointent respectivement vers le premier élément correspondant du tableau atomique. Supposons que les deux pointeurs soient nommés leftIdx et rightIdx, puis leftIdx = 0 (correspondant au premier élément [3] dans copiedArray), rightIdx = 4 ( correspondant au cinquième élément [1] dans copiéArray);
3) Comparez les valeurs des éléments du tableau pointés par leftIdx et rightIdx, sélectionnez le plus petit et attribuez sa valeur à la position correspondante i dans le tableau d'origine. Une fois l'affectation terminée, effectuez une opération d'auto-incrémentation sur le. deux index participant à l'affectation. Si la valeur leftIdx ou rigthIdx a atteint la fin du tableau correspondant, il ne reste plus qu'à copier les éléments restants du tableau vers les positions restantes dans l'ordre.
Voici un exemple précis de fusion :
Premier voyage :
Tableau auxiliaire [21, 28, 39 | 35, 38] (le tableau est divisé en deux sous-tableaux gauche et droit, séparés par |)
[21, , , , ] (La première fois que 21 est comparé à 35, le sous-tableau gauche gagne, leftIdx = 0, i = 0)
Deuxième voyage :
Réseau auxiliaire [21, 28, 39 | 35, 38]
[21, 28, , , ] (La deuxième fois que 28 est comparé à 35, le sous-tableau gauche gagne, leftIdx = 1, i = 1)
Troisième voyage : [21, 28, 39 |
[21, 28, 35, , ] (La troisième fois que 39 est comparé à 35, le sous-tableau de droite gagne, rightIdx = 0, i = 2)
Le quatrième voyage : [21, 28, 39 | 35, 38]
[21, 28, 35, 38,] (La quatrième fois que 39 et 38 sont comparés, le sous-tableau de droite gagne, rightIdx = 1, i = 3)
Le cinquième voyage : [21, 28, 39 | 35, 38]
[21, 28, 35, 38, 39] (Le sous-tableau droit a été copié pour la cinquième fois, pas besoin de comparer leftIdx = 2, i = 4)
Ce qui précède est un processus de fusion. Nous pouvons diviser l'ensemble du tableau qui doit être trié un nombre limité de fois (divisé en deux à chaque fois) jusqu'à ce qu'il soit divisé en un petit tableau d'une longueur de 1. Lorsque la longueur est de 1, le tableau n'a plus besoin d'être trié. Après cela, ces tableaux sont fusionnés dans l'ordre inverse (en raison de la récursion) jusqu'à ce que le dernier sous-tableau de longueur n/2 soit fusionné. Une fois la fusion terminée, le tri des tableaux est également terminé.
Le tri par fusion nécessite le plus d'espace supplémentaire de tous les tris, et chaque fusion nécessite le même nombre d'éléments que la somme des longueurs des deux tableaux participant à la fusion (afin de fournir un tableau auxiliaire). On peut alors en déduire que la complexité spatiale du tri par fusion est de 1 + 2 + 4 + ... + n = n * ( n + 2) / 4 (en ignorant le jugement de parité de n). La complexité temporelle est difficile à estimer. . Ici, j'ai aussi oublié combien ().
Code d'implémentation :
Copiez le code comme suit :
/**
* Fusionner le tri
*/
MERGE(nouveau Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
this.sort(array, 0, array.length 1, ascend);
}
private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {
// OPTIMISER UN
// si la longueur de la sous-chaîne est inférieure à 20,
// utilise le tri par insertion pour réduire les invocations récursives
si (salut bas < 20) {
pour (int i = lo + 1; i <= salut; i++) {
T toInsert = tableau[i];
int j = je;
pour (; j > lo; j) {
int comparer = array[j - 1].compareTo(toInsert);
if (comparer == 0 || comparer < 0 == monter) {
casser;
}
tableau[j] = tableau[j - 1];
}
array[j] = toInsérer ;
}
retour;
}
int mid = lo + (salut lo) / 2;
sort(array, lo, mid, ascend);
sort(array, mid + 1, salut, ascend);
fusionner (tableau, bas, milieu, salut, monter);
}
private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {
// OPTIMISER DEUX
// s'il est déjà dans le bon ordre, ignore cette fusion
// puisque ce n'est pas nécessaire
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == monter) {
retour;
}
@SuppressWarnings("non coché")
T[] arrayCopy = (T[]) new Comparable[salut - bas + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0 ;
int highIdx = mi-lo + 1 ;
pour (int je = lo; je <= salut; i++) {
si (lowIdx > mi-lo) {
// sous-tableau gauche épuisé
array[i] = arrayCopy[highIdx++];
} sinon si (highIdx > salut lo) {
// sous-tableau droit épuisé
array[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
array[i] = arrayCopy[lowIdx++];
} autre {
array[i] = arrayCopy[highIdx++];
}
}
}
})
6. Tri rapide
Le tri rapide est également un algorithme de tri « diviser pour régner » implémenté à l'aide de la méthode de fusion. Son charme est qu'il peut déterminer la position finale correcte du tri pour un élément du tableau dans chaque partition (le cœur de l'algorithme de tri) (une fois). Si le positionnement est précis, cet élément ne sera pas pris en compte au cycle suivant).