C#을 사용하여 기수 정렬 알고리즘을 작성하는 방법

C#을 사용하여 기수 정렬 알고리즘을 작성하는 방법

소개:
Radix 정렬은 정수 정렬에 적합한 비비교 정렬 알고리즘입니다. 기본 아이디어는 정렬할 요소를 낮은 순서에서 높은 순서로 정렬하여 정렬된 순서를 얻는 것입니다. 다른 정렬 알고리즘과 비교하여 기수 정렬은 시간 복잡도와 안정성이 낮습니다.

구현 단계:

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!