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();
    }
}

위 코드에서는 먼저 정렬할 시퀀스에서 최대값과 최소값을 찾은 다음 보조 배열 개수를 만듭니다. 각 요소의 발생 횟수를 계산합니다. 다음으로, 보조 배열에 대해 합 연산을 수행하여 정렬된 순서의 각 요소의 위치를 ​​구합니다. 마지막으로 보조 배열의 통계 결과에 따라 요소를 원래 배열에 다시 넣어 정렬을 완료합니다.

테스트 코드에서는 샘플 배열을 사용하여 카운팅 정렬 알고리즘을 테스트합니다. 출력에는 원래 배열과 정렬된 결과가 표시됩니다.

위의 코드 예제를 통해 C#에서 개수 정렬 알고리즘을 구현하는 방법을 이해할 수 있습니다. 카운팅 정렬은 간단하지만 효과적인 정렬 알고리즘으로, 특히 정렬할 시퀀스의 요소 범위가 작은 상황에 적합합니다. 카운팅 정렬 알고리즘의 원리와 구현을 익히면 정렬이 필요할 때 가장 적합한 정렬 알고리즘을 선택하고 프로그램의 효율성을 높일 수 있습니다.

위 내용은 C#에서 계산 정렬 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!