Реализовать карманную (блочную) сортировку — C#(Си шарп)

using System;
using System.Collections.Generic;
 
namespace ConsoleApp1
{
    class Program
    {
        static void BucketSort(int[] a)
        {
            // Примем, что количество корзин равно количеству элементов в массиве-источнике.
            // Тогда:
            // массив корзин
            List<int>[] aux = new List<int>[a.Length];
 
            // каждую корзину проинициализировать
            for (int i = 0; i < aux.Length; ++i)
                aux[i] = new List<int>();
 
            // найти диапазон значений в массиве-источнике
            int minValue = a[0];
            int maxValue = a[0];
 
            for (int i = 1; i < a.Length; ++i)
            {
                if (a[i] < minValue)
                    minValue = a[i];
                else if (a[i] > maxValue)
                    maxValue = a[i];
            }
 
            // эта величина будет использоваться a.Length раз, поэтому имеет смысл её сохранить.
            double numRange = maxValue - minValue;
 
            for (int i = 0; i < a.Length; ++i)
            {
                // вычисление индекса корзины
                int bcktIdx = (int)Math.Floor((a[i] - minValue) / numRange * (aux.Length - 1));
 
                // добавление элемента в соответствующую корзину
                aux[bcktIdx].Add(a[i]);
            }
 
            // сортировка корзин. Здесь я, для упрощения себе писанины, использую библиотечную сортировку
            for (int i = 0; i < aux.Length; ++i)
                aux[i].Sort();
 
            // собираем отсортированные элементы обратно в массив-источник
            int idx = 0;
 
            for (int i = 0; i < aux.Length; ++i)
            {
                for (int j = 0; j < aux[i].Count; ++j)
                    a[idx++] = aux[i][j];
            }
        }
 
        static void Main()
        {
            int[] arr = new int[15];
            Random rnd = new Random();
 
            for (int i = 0; i < arr.Length; ++i)
                arr[i] = rnd.Next(-99, 100);
 
            Console.WriteLine(String.Join(" ", arr));
            BucketSort(arr);
            Console.WriteLine(String.Join(" ", arr));
        }
    }
}

Leave a Comment