So implementieren Sie den Zählsortieralgorithmus in C#

So implementieren Sie den Zählsortieralgorithmus in C#

Zählsortierung ist ein einfacher, aber effektiver Sortieralgorithmus, der eine Menge von Ganzzahlen in einer Zeitkomplexität von O(n+k) sortieren kann, wobei n die Anzahl der Elemente ist sortiert werden, k ist der Bereich der zu sortierenden Elemente.

Die Grundidee der Zählsortierung besteht darin, ein Hilfsarray zu erstellen, um die Anzahl der Vorkommen jedes Elements in der zu sortierenden Sequenz zu zählen. Anschließend wird durch Ausführen einer Summenoperation am Hilfsarray die Position jedes Elements in der geordneten Sequenz ermittelt. Basierend auf den statistischen Ergebnissen des Hilfsarrays werden die Elemente schließlich wieder in das ursprüngliche Array eingefügt, um die Sortierung abzuschließen.

Das Folgende ist ein spezifisches Codebeispiel zum Implementieren des Zählsortieralgorithmus in 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();
    }
}

Im obigen Code ermitteln wir zunächst die Maximal- und Minimalwerte in der zu sortierenden Sequenz und erstellen dann eine Hilfsarray-Zählung um die Anzahl der Vorkommen jedes Elements zu zählen. Als nächstes wird die Position jedes Elements in der geordneten Sequenz ermittelt, indem eine Summenoperation für das Hilfsarray durchgeführt wird. Basierend auf den statistischen Ergebnissen des Hilfsarrays werden die Elemente schließlich wieder in das ursprüngliche Array eingefügt, um die Sortierung abzuschließen.

Im Testcode verwenden wir ein Beispielarray, um den Zählsortieralgorithmus zu testen. Die Ausgabe zeigt das ursprüngliche Array und die sortierten Ergebnisse.

Anhand der obigen Codebeispiele können wir verstehen, wie der Zählsortieralgorithmus in C# implementiert wird. Counting Sort ist ein einfacher, aber effektiver Sortieralgorithmus, der sich besonders für Situationen eignet, in denen der Bereich der zu sortierenden Elemente in der Sequenz klein ist. Durch die Beherrschung der Prinzipien und der Implementierung von Zähl- und Sortieralgorithmen können wir bei Bedarf den am besten geeigneten Sortieralgorithmus auswählen und die Effizienz des Programms verbessern.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Zählsortieralgorithmus in C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!