1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | 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)); } }} |