Comment implémenter un algorithme de tri par comptage en C#

Comment implémenter un algorithme de tri par comptage en C#

Le tri par comptage est un algorithme de tri simple mais efficace qui peut trier un ensemble d'entiers dans une complexité temporelle de O(n+k), où n est le nombre d'éléments à être trié, k est la plage d’éléments à trier.

L'idée de base du tri par comptage est de créer un tableau auxiliaire pour compter les occurrences de chaque élément de la séquence à trier. Ensuite, en effectuant une opération de somme sur le tableau auxiliaire, la position de chaque élément dans la séquence ordonnée est obtenue. Enfin, sur la base des résultats statistiques du tableau auxiliaire, les éléments sont remis dans le tableau d'origine pour terminer le tri.

Ce qui suit est un exemple de code spécifique pour implémenter l'algorithme de tri par comptage en C# :

using System;

class CountingSort
{
    public static void Sort(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            return;
        }

        // 找到待排序序列中的最大值和最小值
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i] < min)
            {
                min = array[i];
            }
            if (array[i] > max)
            {
                max = array[i];
            }
        }

        // 创建辅助数组count，用于统计待排序序列中每个元素的出现次数
        int[] count = new int[max - min + 1];

        // 统计每个元素的出现次数
        for (int i = 0; i < array.Length; i++)
        {
            count[array[i] - min]++;
        }

        // 对辅助数组进行求和操作，得到每个元素在有序序列中的位置
        for (int i = 1; i < count.Length; i++)
        {
            count[i] += count[i - 1];
        }

        // 创建临时数组，用于存储排序结果
        int[] sortedArray = new int[array.Length];

        // 根据辅助数组的统计结果，将元素放回原始数组中
        for (int i = array.Length - 1; i >= 0; i--)
        {
            int index = count[array[i] - min] - 1;
            sortedArray[index] = array[i];
            count[array[i] - min]--;
        }

        // 将排序结果拷贝回原始数组
        Array.Copy(sortedArray, array, array.Length);
    }

    // 测试计数排序算法
    static void Main(string[] args)
    {
        int[] array = { 5, 2, 9, 3, 1, 6, 8, 4, 7 };
        Console.WriteLine("原始数组：");
        PrintArray(array);
        Sort(array);
        Console.WriteLine("排序结果：");
        PrintArray(array);
    }

    // 打印数组
    static void PrintArray(int[] array)
    {
        foreach (int element in array)
        {
            Console.Write(element + " ");
        }
        Console.WriteLine();
    }
}

Dans le code ci-dessus, nous trouvons d'abord les valeurs maximales et minimales dans la séquence à trier, puis créons un nombre de tableau auxiliaire pour compter le nombre d'occurrences de chaque élément. Ensuite, la position de chaque élément dans la séquence ordonnée est obtenue en effectuant une opération de somme sur le tableau auxiliaire. Enfin, sur la base des résultats statistiques du tableau auxiliaire, les éléments sont remis dans le tableau d'origine pour terminer le tri.

Dans le code de test, nous utilisons un exemple de tableau pour tester l'algorithme de tri par comptage. La sortie affiche le tableau d'origine et les résultats triés.

Grâce aux exemples de code ci-dessus, nous pouvons comprendre comment implémenter l'algorithme de tri par comptage en C#. Le tri par comptage est un algorithme de tri simple mais efficace, particulièrement adapté aux situations où la plage d'éléments de la séquence à trier est petite. En maîtrisant les principes et la mise en œuvre des algorithmes de tri par comptage, nous pouvons choisir l'algorithme de tri le plus approprié lorsque le tri est nécessaire et améliorer l'efficacité du programme.

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!