Algorithme de tri : tri par fusion [avec code]

Qu'est-ce que le tri par fusion ?

En termes simples, le tri par fusion consiste à intégrer deux séquences ordonnées ensemble.

Tutoriel recommandé : Tutoriel vidéo PHP

Comment combiner deux séquences ordonnées les intégrer ensemble ?

Alors on suppose qu'il y a M=｛m1,m2,m3,....,mx｝ séquence et N =｛n1,n2,n3,...., ny} séquence, ces deux séquences sont déjà des séquences ordonnées. Créez d'abord une séquence vide K = {}, puis comparez m1 et n1, ajoutez m1 < n1, puis mettez m1 dans la séquence K, puis M Le curseur de séquence recule. , c'est-à-dire que m2 et n1 seront comparés la prochaine fois jusqu'à ce que toutes les comparaisons soient terminées et remplies dans la séquence K.

Puisque le tri par fusion intègre des séquences ordonnées, cela ne signifie-t-il pas que les séquences non ordonnées ne peuvent pas être triées ? Cette condition n'est-elle pas trop sévère ?

Le tri par fusion est basé sur la méthode diviser pour régner, c'est-à-dire qu'une séquence complètement désordonnée peut être divisée sans fil pour obtenir une séquence ordonnée. Par exemple : il y a maintenant M={m1. , m2, m3, ...., mx}, la séquence M est une séquence complètement désordonnée, alors la séquence M peut être divisée en plusieurs petites séquences - {m1, m2}, {m3, m4 }....{ mx-1, mx} ; À ce stade, ces séquences sont dans l'ordre, elles peuvent ensuite être triées via l'opération de fusion, donc le tri par fusion peut également trier les séquences non ordonnées, et sa vitesse est juste derrière le tri rapide, qui appartient à Stable. tri.

Comment diviser une séquence ?

Comme mentionné dans la question précédente, le tri par fusion est basé sur diviser pour régner, et diviser pour régner se reflète dans la séquence de division. Par exemple : il y a maintenant M = {m1, m2, m3, ...., mx}, la première division : M1 = {m1, m2, ..., m(x+1)/2}, M2 = {m(x+1 )/2 +1 , m(x+1)/2 +2,...,mx}, après la première division, les séquences M1 et M2 sont obtenues, puis les M1 et M2 sont divisés, et après plusieurs divisions, x/2 est obtenu + x%2 séquences, puis fusionnez-les une par une.

Les étapes spécifiques de cet algorithme :

1. Spécifiez les premiers pointeurs gauche et milieu (la gauche pointe vers le premier élément de la séquence 1 , la droite pointe vers la séquence 2 (le premier élément)

2. Comparez les tailles de gauche et du milieu et placez les petits éléments dans le nouvel espace

3. Répétez l'étape 2 jusqu'à ce que l'un des les séquences ont été parcourues

　4. Copiez et collez les éléments restants qui n'ont pas été ajoutés au nouvel espace directement dans le nouvel espace

Les étapes principales de l'algorithme :

1. Utilisez la méthode diviser pour régner (récursion) pour diviser la séquence

2. Comparez les tailles de gauche et de milieu et ajoutez de petits éléments dans le nouveau espace

indique Terminé, collez le code :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 排序__归并排序
{
    class 归并
    {

        public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
        static void Main(string[] args)
        {
            Sort(arr, 0, arr.Length -1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }

        public static void Sort(int []a,int left,int right)
        {
            if (left >= right) return;
            else
            {
                int mid = (left + right) / 2;                //@1
                Sort(a, left, mid);
                Sort(a, mid + 1, right);
                MergeSort(a, left, mid, right);
            }
        }

        public static void MergeSort(int []a,int left,int mid,int right)
        {
            int[] Arr = new int[right - left + 1];
            int l = left, m = mid +1 , k = 0;           //@2
            while ( m <= right && l <= mid )          //@3
            {
                if (a[l] > a[m]) Arr[k++] = a[m++];
                else Arr[k++] = a[l++];
            }
            while (m < right +1)                           //@4
            {
                Arr[k++] = a[m++];
            }
            while (l < mid +1 )  Arr[k++] = a[l++];        //@4
            for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k];
        }
    }
}

Interprétation du code :

@1 : La fonction Sort() termine la segmentation de la séquence. Chaque récursion divise la séquence en deux moitiés jusqu'à ce qu'elle soit divisée en deux. ne peut pas être séparé.

@2 : l représente le premier élément de la séquence 1, m représente le premier élément de la séquence 2, k représente le nombre d'éléments existants dans le nouveau tableau Arr

@3 : le premier élément de la séquence 1 Comparez avec le premier élément de la séquence 2, mettez le petit dans Arr et déplacez le curseur de la séquence vers l'arrière jusqu'à ce que les éléments de l'une des séquences soient comparés

　@4 : Le processus de comparaison entre la séquence 1 et la séquence 2, il peut sembler que la séquence 1 a toutes été ajoutées à Arr, mais pas la séquence 2, alors les éléments non comparés restants seront copiés directement dans Arr

Résumé :

Le code ci-dessus ne divise pas le tableau au vrai sens du terme. Il effectue simplement une division logique. Il ne remplit pas le tableau divisé dans un nouveau tableau comme les autres codes. Cela aura un léger impact sur la vitesse et la mémoire. Bien que ce soit minime, ce n'est pas si bon après tout. Dans l'opération de fusion, vous devez faire attention aux paramètres qui ne franchissent pas la limite (j'ai longtemps réfléchi à la raison pour laquelle le m au-dessus de @2 devrait être égal à mi +1. au lieu de mid En fait, la raison est très simple Parce que mid appartient à la séquence de gauche, il n'appartient qu'à la séquence de droite à partir de mid+1. Changer m = mid +1 en m = mid n'est pas impossible, mais le. le code suivant doit également être modifié, mais il n'est pas nécessaire de faire une autre comparaison inutile. Ce problème, j'y ai vraiment réfléchi pendant longtemps...), en fait, tant que la relation logique est clarifiée, le code peut être facilement saisi.

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!