Comment écrire un algorithme de tri par base en utilisant C#

Comment utiliser C# pour écrire un algorithme de tri par base

Introduction :
Radix Sort est un algorithme de tri non comparatif adapté au tri d'entiers. Son idée de base est de trier les éléments à trier de bas en haut pour obtenir une séquence ordonnée. Comparé à d’autres algorithmes de tri, le tri par base a une complexité temporelle et une stabilité moindres.

Étapes de mise en œuvre :

1. Trouvez le plus grand nombre du tableau à trier et déterminez son nombre de chiffres.
2. En fonction du nombre maximum de chiffres, passez à l'étape suivante de bas en haut.
3. Effectuez un tri par comptage sur le tableau à trier et regroupez en fonction du nombre actuel.
4. Recombinez le tableau groupé en un nouveau tableau à trier.
5. Répétez les étapes 3 et 4 jusqu'à ce que tous les chiffres aient été comparés.

Exemple de code :
Ce qui suit est un exemple de code pour l'algorithme de tri par base écrit en C# :

using System;

public class RadixSort
{
    public static void Sort(int[] array)
    {
        int max = GetMaxValue(array);
        int digits = GetDigits(max);

        for (int i = 0; i < digits; i++)
        {
            CountingSort(array, i);
        }
    }

    private static int GetMaxValue(int[] array)
    {
        int max = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i] > max)
            {
                max = array[i];
            }
        }
        return max;
    }

    private static int GetDigits(int number)
    {
        int digits = 0;
        while (number > 0)
        {
            number /= 10;
            digits++;
        }
        return digits;
    }

    private static void CountingSort(int[] array, int digit)
    {
        int[] count = new int[10];
        int[] sortedArray = new int[array.Length];

        for (int i = 0; i < array.Length; i++)
        {
            int digitValue = GetDigitValue(array[i], digit);
            count[digitValue]++;
        }

        for (int i = 1; i < count.Length; i++)
        {
            count[i] += count[i - 1];
        }

        for (int i = array.Length - 1; i >= 0; i--)
        {
            int digitValue = GetDigitValue(array[i], digit);
            int index = count[digitValue] - 1;
            sortedArray[index] = array[i];
            count[digitValue]--;
        }

        for (int i = 0; i < array.Length; i++)
        {
            array[i] = sortedArray[i];
        }
    }

    private static int GetDigitValue(int number, int digit)
    {
        for (int i = 0; i < digit; i++)
        {
            number /= 10;
        }
        return number % 10;
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        int[] array = { 170, 45, 75, 90, 802, 24, 2, 66 };
        
        Console.WriteLine("Before sorting:");
        foreach (int num in array)
        {
            Console.Write(num + " ");
        }
        
        RadixSort.Sort(array);
        
        Console.WriteLine("

After sorting:");
        foreach (int num in array)
        {
            Console.Write(num + " ");
        }
    }
}

Résultat d'exécution :

Before sorting:
170 45 75 90 802 24 2 66 

After sorting:
2 24 45 66 75 90 170 802

Résumé :
L'algorithme de tri par base est un algorithme de tri relativement efficace qui peut effectuer des opérations sur des nombres entiers. tableaux Tri rapide. En triant le tableau à trier de bas en haut, un tableau ordonné est finalement obtenu. Lorsque nous utilisons C# pour écrire un algorithme de tri de base, nous devons d'abord trouver la valeur maximale et le nombre de chiffres du tableau à trier, puis compter et trier chaque chiffre, et enfin recombiner le tableau trié pour obtenir un résultat ordonné. Comme le montrent les résultats d’exécution de l’exemple de code, l’algorithme de tri par base peut trier correctement le tableau.

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!