Aperçu de l'algorithme / idées
Le tri de fusion est basé sur une stratégie appelée "Diviser et conquérir". L'idée de base est la suivante:
1. Pour deux tableaux commandés, pour les fusionner dans un tableau ordonné, nous pouvons facilement écrire le code suivant:
// A et B est Ascend.public void Merge (int [] a, int [] b, int [] c) {int i = 0, j = 0, k = 0; while (i <= a.length && j <= b.length) {if (a [i] <= b [i]) {c [k ++] = a [i ++]; } else {c [k ++] = b [j ++]; }} while (i <= a.length) {c [k ++] = a [i ++]; }} Il est facile de voir qu'un tel algorithme de fusion est efficace et sa complexité temporelle peut atteindre O (n).
2. S'il existe un tableau non ordonné qui doit être trié, mais ses deux sous-réseaux complètement divisés A et B sont commandés séparément, nous pouvons également les implémenter facilement à l'aide du code ci-dessus;
3. Alors, que dois-je faire si A et B sont désordonnés? Vous pouvez les diviser en tableaux plus petits.
4. Si vous le divisez jusqu'au plus petit, chaque sous-réseau n'a qu'un seul élément, il peut être considéré comme un tableau ordonné.
5. Commencez par ces plus petits tableaux, fusionnez-les contre les étapes ci-dessus, et l'ensemble du tableau est organisé.
En bref, le tri de fusion consiste à utiliser la récursivité, à décomposer d'abord le tableau dans un sous-réseau, puis à fusionner le tableau.
exemple
Voici un exemple. Si vous souhaitez trier le tableau A = {2,1,3,5,2,3}, divisez le tableau en deux sous-réseaux: {2,1,3} et {5,2,3}. Après avoir trié ces deux sous-réseaux, ils deviennent {1,2,3} et {2,3,5}, puis fusionnent les deux tableaux pour obtenir le tableau ordonné final. L'implémentation du code est la suivante:
void tri (int [] a) {int [] Aux = new int [a.Length]; // AUX Array Mergesort (A, 0, A.Length - 1, Aux);} void Mergesort (int [] a, int lo, int hi, int [] Aux) {if (hi <= lo) return; int mid = lo + (hi - lo) / 2; Mergesort (A, Lo, Mid, Aux); Mergesort (A, Mid + 1, Hi, Aux); Merge (A, Lo, Mid, Hi, Aux);} void Merge (int [] a, int lo, int mid, int hi, int [] Aux) {int i = lo, j = mid + 1; pour (int k = lo; k <= hi; k ++) {Aux [k] = a [k]; } pour (int k = lo; k <= hi; k ++) {if (i> mid) a [k] = aux [j ++]; else if (j> hi) a [k] = Aux [i ++]; else if (Aux [i] <= Aux [j]) a [k] = Aux [i ++]; else a [k] = Aux [j ++]; }} Une autre implémentation: tri de fusion ascendante
Dans la mise en œuvre ci-dessus, il équivaut à diviser un gros problème en petits problèmes et à les résoudre séparément, puis à utiliser les réponses à tous les petits problèmes pour résoudre tout le gros problème. Diviser le type de grand tableau en un petit tableau, le genre de sorte est un type de haut en bas. Il y a une autre implémentation qui est un tri ascendant, c'est-à-dire de fusionner d'abord deux puis de fusionner quatre et quatre ... l'implémentation du code est la suivante:
void tri (int [] a) {int n = a.Length; int [] Aux = new int [n]; pour (int sz = 1; sz <n; sz + = sz) {for (int lo = 0; lo <n - sz; lo + = sz + sz) {// Dans chaque manche de fusion, le deuxième sous-tableau qui a été fusionné la dernière fois peut être plus petit que la première fusion de sous-argent (a, lo, lo + sz - 1, math.Min (lo + sz + sz - 1, n - 1), Aux); }}}