Алгоритм точного поиска и сортировки C #: упражнение 10 с решением
Напишите программу C # Sharp для сортировки списка элементов с использованием алгоритма сортировки Radix.
Radix sort — это несравнительный алгоритм целочисленной сортировки, который сортирует данные с целочисленными ключами путем группировки ключей по отдельным цифрам, которые имеют одинаковую значащую позицию и значение.
Пример:
Исходный, несортированный список: 272, 45, 75, 81, 501, 2, 24, 66
Сортировка по наименьшей значащей цифре (разряды единиц) дает:
27 2 , 8 1, 50 1 , 2 , 2 4, 4 5, 7 5, 6 6
Здесь мы сохраняем 501 перед 2, потому что 501 произошло перед 2 в исходном списке, и аналогично для пар 272 & 81 и 45 & 75.
Сортировка по следующей цифре (10 с место) дает:
501, 2, 2 4, 4 5, 6 6, 272, 7 5, 9
Обратите внимание, что 501 снова стоит перед 2, поскольку 501 стоит перед 2 в предыдущем списке.
Сортировка по старшей цифре (место 100 ) дает:
2, 24, 45, 66, 75, 81, 2 72, 5 01
Важно понимать, что каждый из вышеперечисленных шагов требует всего одного прохода по данным, поскольку каждый элемент может быть помещен в его правильную корзину без необходимости сравнивать с другими элементами.
Некоторые реализации поразрядной сортировки выделяют пространство для сегментов, сначала подсчитывая количество ключей, которые принадлежат каждому сегменту, прежде чем перемещать ключи в эти сегменты. Количество повторений каждой цифры сохраняется в массиве.. Рассмотрим предыдущий список ключей, рассматриваемых по-другому:
272, 045, 075, 081, 002, 024, 501, 066
Начинается первый проход подсчета по младшей значащей цифре каждого ключа, создавая массив размеров сегмента:
- 2 (размер сегмента для цифр 0: 272, 081)
- 2 (размер сегмента для цифр 2: 002, 501)
- 1 (размер сегмента для цифр 4: 024)
- 2 (размер сегмента для цифр из 5: 045, 075)
- 1 (размер сегмента для цифр 6: 066)
Второй проход счета на следующей более значащей цифре каждого ключа создаст массив размеров сегмента:
- 2 (размер сегмента для цифр 0: 002, 501)
- 1 (сегмент размер для цифр 2: 024)
- 1 (размер сегмента для цифр 4: 045)
- 1 (размер сегмента для цифр 6: 066)
- 2 (размер сегмента для цифр 7: 272, 075)
- 1 (размер сегмента для цифр 9: 081
Третий и последний проход подсчета наиболее значащей цифры каждого ключа будет создать массив размеров сегмента:
- 6 (размер сегмента для цифр 0: 002, 024, 045, 066, 075, 081)
- 1 (размер сегмента для цифр 1: 272)
- 1 (размер сегмента для цифр 8: 501)
Пример решения : —
C # Sharp Code:
using System; пространство имен Radix_Sort {класс Program {static void Sort (int [] arr) {int i, j; int [] tmp = новый int [arr.Length]; для (int shift = 31; shift> -1; --shift) {j = 0; for (i = 0; i = 0; if (shift == 0?! move: move) arr [ij] = arr [i]; else tmp [j ++] = arr [i];} Array.Copy (tmp, 0, arr, arr.Length-j, j);}} static void Main (string [] args) {int [] arr = new int [] {2, 5, -4, 11, 0, 18, 22, 67, 51, 6}; Console.WriteLine (" nOriginal array:"); foreach (var item in arr) {Console.Write ("" + item);} Sort (arr); Console.WriteLine (" nSorted array: "); foreach (var item in arr) {Console.Write (" "+ item);} Console.WriteLine (" n ");}}}
Пример вывода:
Исходный массив: 2 5-4 11 0 18 22 67 51 6 Сортированный массив: -4 0 2 5 6 11 18 22 51 67
Схема:
Редактор кода C # Sharp:
Предыдущий: Напишите программу C # Sharp для сортировки списка элементов с помощью быстрой сортировки
Далее: Напишите Программа C # Sharp для сортировки списка элементов с использованием алгоритма сортировки по выбору.
