Упражнения по алгоритму точного поиска и сортировки в C #: Радиксная сортировка

Алгоритм точного поиска и сортировки 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 для сортировки списка элементов с использованием алгоритма сортировки по выбору.

Оцените статью
nanomode.ru
Добавить комментарий