So schreiben Sie einen Basissortieralgorithmus mit C#

So schreiben Sie mit C# einen Radix-Sortieralgorithmus

Einführung:
Radix Sort ist ein nicht vergleichender Sortieralgorithmus, der zum Sortieren von Ganzzahlen geeignet ist. Seine Grundidee besteht darin, die zu sortierenden Elemente von niedrig nach hoch zu sortieren, um eine geordnete Reihenfolge zu erhalten. Im Vergleich zu anderen Sortieralgorithmen weist die Radix-Sortierung eine geringere zeitliche Komplexität und Stabilität auf.

Implementierungsschritte:

1. Finden Sie die größte Zahl im zu sortierenden Array und bestimmen Sie deren Anzahl an Ziffern.
2. Fahren Sie je nach maximaler Ziffernzahl mit dem nächsten Schritt von niedrig nach hoch fort.
3. Führen Sie eine Zählsortierung für das zu sortierende Array durch und gruppieren Sie es entsprechend der aktuellen Nummer.
4. Kombinieren Sie das gruppierte Array erneut zu einem neuen Array, das sortiert werden soll.
5. Wiederholen Sie die Schritte 3 und 4, bis alle Ziffern verglichen wurden.

Codebeispiel:
Das Folgende ist ein Beispielcode für den in C# geschriebenen Basissortieralgorithmus:

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 + " ");
        }
    }
}

Laufendes Ergebnis:

Before sorting:
170 45 75 90 802 24 2 66 

After sorting:
2 24 45 66 75 90 170 802

Zusammenfassung:
Der Basissortierungsalgorithmus ist ein relativ effizienter Sortieralgorithmus, der Operationen für Ganzzahlen ausführen kann Arrays Schnelle Sortierung. Durch Sortieren des zu sortierenden Arrays von niedrig nach hoch wird schließlich ein geordnetes Array erhalten. Wenn wir C# zum Schreiben eines Basissortieralgorithmus verwenden, müssen wir zunächst den Maximalwert und die Anzahl der zu sortierenden Ziffern des Arrays ermitteln, dann jede Ziffer zählen und sortieren und schließlich das sortierte Array neu kombinieren, um ein geordnetes Ergebnis zu erhalten. Wie aus den laufenden Ergebnissen des Beispielcodes hervorgeht, kann der Radix-Sortieralgorithmus das Array korrekt sortieren.

Das obige ist der detaillierte Inhalt vonSo schreiben Sie einen Basissortieralgorithmus mit C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!