Comment implémenter l'algorithme de tri par fusion en C#

Comment implémenter l'algorithme de tri par fusion en C#

Le tri par fusion est un algorithme de tri classique basé sur l'idée de diviser pour régner. Il divise un gros problème en plusieurs petits problèmes, puis résout progressivement les petits problèmes et fusionne les résultats. . Tri complet. Ce qui suit présente comment implémenter l’algorithme de tri par fusion en C# et fournit des exemples de code spécifiques.

L'idée de base du tri par fusion est de diviser la séquence à trier en plusieurs sous-séquences, de les trier séparément, puis de fusionner les sous-séquences triées en une séquence ordonnée. La clé de cet algorithme est de mettre en œuvre les opérations de fractionnement et de fusion des sous-séquences.

Tout d'abord, nous devons écrire une fonction récursive pour implémenter l'opération de division, diviser la séquence originale en deux sous-séquences et appeler récursivement l'algorithme de tri par fusion pour trier les sous-séquences. Le code spécifique est le suivant :

static void MergeSort(int[] array, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        MergeSort(array, left, middle);
        MergeSort(array, middle + 1, right);
        Merge(array, left, middle, right);
    }
}

Ensuite, nous devons écrire une fonction de fusion pour fusionner deux sous-séquences ordonnées en une seule séquence ordonnée. La clé de l'opération de fusion est de comparer les éléments des deux sous-séquences et de les placer dans un tableau auxiliaire par ordre de taille. Le code spécifique est le suivant :

static void Merge(int[] array, int left, int middle, int right)
{
    int[] temp = new int[array.Length];
    int i = left;
    int j = middle + 1;
    int k = left;

    while (i <= middle && j <= right)
    {
        if (array[i] <= array[j])
        {
            temp[k] = array[i];
            i++;
        }
        else
        {
            temp[k] = array[j];
            j++;
        }
        k++;
    }

    while (i <= middle)
    {
        temp[k] = array[i];
        i++;
        k++;
    }

    while (j <= right)
    {
        temp[k] = array[j];
        j++;
        k++;
    }

    for (int l = left; l <= right; l++)
    {
        array[l] = temp[l];
    }
}

Enfin, nous pouvons trier le tableau à trier en appelant la fonction MergeSort. Le code spécifique est le suivant :

static void Main(string[] args)
{
    int[] array = { 5, 3, 8, 4, 2, 1, 9, 7, 6 };
    MergeSort(array, 0, array.Length - 1);

    Console.WriteLine("排序后的数组：");
    for (int i = 0; i < array.Length; i++)
    {
        Console.Write(array[i] + " ");
    }

    Console.ReadLine();
}

Ce qui précède sont les étapes détaillées et des exemples de code pour implémenter le tri par fusion. algorithme en C#. En divisant récursivement la séquence, en triant les sous-séquences et en fusionnant les résultats, nous pouvons trier efficacement des séquences de n'importe quelle taille. La complexité temporelle du tri par fusion est O(nlogn), qui est un algorithme de tri relativement rapide.

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!