C# を使用して基数ソート アルゴリズムを作成する方法

C# を使用して基数ソート アルゴリズムを作成する方法

はじめに:
基数ソート (基数ソート) は、整数のソートに適した非比較ソート アルゴリズムです。 。その基本的な考え方は、並べ替えられる要素を低いものから高いものに並べ替えて、順序付けられたシーケンスを取得することです。他の並べ替えアルゴリズムと比較して、基数並べ替えは時間の複雑さが低く、安定性が低くなります。

実装手順:

1. 並べ替える配列内で最大の数値を見つけ、その桁数を決定します。
2. 最大桁数に従って、下位から上位へ次のステップに進みます。
3. ソート対象の配列に対してカウントソートを実行し、現在の番号に従ってグループ化します。
4. グループ化された配列を、並べ替えられる新しい配列に再結合します。
5. すべての桁が比較されるまで、手順 3 と 4 を繰り返します。

コード サンプル:
次は、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 + " ");
        }
    }
}

実行結果:

Before sorting:
170 45 75 90 802 24 2 66 

After sorting:
2 24 45 66 75 90 170 802

概要:
基数ソート アルゴリズムは、整数配列を迅速にソートできる比較的効率的なソート アルゴリズムです。ソート対象の配列を下位から上位にソートすることで、最終的に順序付けられた配列が得られます。 C# を使用して基数ソート アルゴリズムを作成する場合、まずソートする配列の最大値と桁数を見つけ、次に各桁を数えてソートし、最後にソートされた配列を再結合して順序付けされた結果を取得する必要があります。サンプル コードの実行結果からわかるように、基数ソート アルゴリズムは配列を正しくソートできます。

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