C# でカウントソートアルゴリズムを実装する方法

C でカウンティング ソート アルゴリズムを実装する方法

#カウンティング ソートは、O(n k) 時間の計算量を達成できるシンプルだが効果的なソート アルゴリズムです。整数のセットをソートします。ここで、n は並べ替えられる要素の数、k は並べ替えられる要素の範囲です。

カウントソートの基本的な考え方は、ソートされるシーケンス内の各要素の出現数をカウントするための補助配列を作成することです。次に、補助配列に対して合計演算を実行することにより、順序付けられたシーケンス内の各要素の位置が取得されます。最後に、補助配列の統計結果に基づいて、要素を元の配列に戻して並べ替えを完了します。

以下は、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();
    }
}

上記のコードでは、まず並べ替えられるシーケンス内の最大値と最小値を見つけます。 、次に、各要素の出現をカウントするための補助配列 count を作成します。次に、補助配列に対して合計演算を実行することにより、順序付けられたシーケンス内の各要素の位置が取得されます。最後に、補助配列の統計結果に基づいて、要素を元の配列に戻して並べ替えを完了します。

テスト コードでは、サンプル配列を使用してカウント並べ替えアルゴリズムをテストします。出力には、元の配列と並べ替えられた結果が表示されます。

上記のコード例を通じて、C# でカウント並べ替えアルゴリズムを実装する方法を理解できます。カウンティング ソートはシンプルですが効果的なソート アルゴリズムであり、ソートされるシーケンス内の要素の範囲が狭い状況に特に適しています。カウントソートアルゴリズムの原理と実装をマスターすることで、ソートが必要なときに最適なソートアルゴリズムを選択し、プログラムの効率を向上させることができます。

以上がC# でカウントソートアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。