Question

Помогите пожалуйста. Нужно написать алгоритм сортировки "Сортировка подсчётом"(Counting Sort) на языке С#. Предпочтительно реализовать через массив​

Answer 1

Ответ:

using System;

class Program

{

   //простой вариант сортировки подсчетом

   static int[] BasicCountingSort(int[] array, int k)

   {

       var count = new int[k + 1];

       for (var i = 0; i < array.Length; i++)

       {

           count[array[i]]++;

       }

       var index = 0;

       for (var i = 0; i < count.Length; i++)

       {

           for (var j = 0; j < count[i]; j++)

           {

               array[index] = i;

               index++;

           }

       }

       return array;

   }

   //метод для получения массива заполненного случайными числами

   static int[] GetRandomArray(int arraySize, int minValue, int maxValue)

   {

       var random = new Random();

       var randomArray = new int[arraySize];

       for (var i = 0; i < randomArray.Length; i++)

       {

           randomArray[i] = random.Next(minValue, maxValue);

       }

       return randomArray;

   }

   static void Main(string[] args)

   {

       var arr = GetRandomArray(10, 0, 9);

       Console.WriteLine("Входные данные: {0}", string.Join(", ", arr));

       Console.WriteLine("Отсортированный массив: {0}", string.Join(", ", BasicCountingSort(arr, 9)));

       Console.ReadLine();

   }

}

Пошаговое объяснение:

Answer 2

Конечно, вот пример реализации сортировки подсчетом (Counting Sort) на языке C# с использованием массива:

csharpCopy code
using System;

class CountingSort
{
    public static void Sort(int[] arr)
    {
        int max = FindMaxValue(arr); // Находим максимальное значение в массиве
        int[] countArray = new int[max + 1]; // Создаем массив для подсчета частот элементов

        foreach (int num in arr)
        {
            countArray[num]++; // Увеличиваем счетчик для текущего элемента
        }

        int outputIndex = 0;
        for (int i = 0; i < countArray.Length; i++)
        {
            while (countArray[i] > 0)
            {
                arr[outputIndex] = i; // Заполняем исходный массив значениями из countArray
                outputIndex++;
                countArray[i]--;
            }
        }
    }

    private static int FindMaxValue(int[] arr)
    {
        int max = arr[0];
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i] > max)
            {
                max = arr[i];
            }
        }
        return max;
    }

    static void Main(string[] args)
    {
        int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
        Console.WriteLine("Исходный массив: ");
        PrintArray(arr);

        Sort(arr);

        Console.WriteLine("Отсортированный массив: ");
        PrintArray(arr);
    }

    private static void PrintArray(int[] arr)
    {
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

Этот код сначала находит максимальное значение в массиве, создает массив countArray для подсчета частот элементов, а затем использует этот массив для сортировки исходного массива. Наконец, результат выводится на экран.