Цифровая сортировка (Radix Sort) (Реализация на C#)

C#   9 июля 2012  Автор статьи:  

Цифровая сортировка или Radix Sort реализована ниже. Программа формирует массив из size случайных элементов, которые генерируются случайным образом из диапазона от nmin до nmax. Затем производится сортировка алгоритмом Radix Sort.
Реализация данного алгоритма на C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sort
{
class Program
{

public static int digit(int n, int p) //получение p-го байта
{
return (n >> (8 * p) & 255);
}

static void Main()
{
Console.WriteLine("Enter the array size: ");
int size = int.Parse(Console.ReadLine()); //размер массива
int[] a = new int [size], //инициализация массивов a и b по size элементов
b = new int [size];

//заполняем массив size случайными числами от nmin до nmax
Console.WriteLine("Enter minimum element: ");
int nmin = int.Parse(Console.ReadLine()); //считывание nmin
Console.WriteLine("Enter maximum element: ");
int nmax = int.Parse(Console.ReadLine()); //считывание nmax
Random gen = new Random(); //перемнная типа Random
for (int i = 0; i < size; i++) { a[i] = gen.Next(nmin, nmax + 1); //генерация случайного элемента из диапазона Console.Write(a[i]); //вывод его на экран Console.Write(' '); } Console.WriteLine("\n"); //максимальноe число байтов в числе int k = sizeof(int); //количество элементов в массиве int n = size; //цикл по всем байтам for (int i = 0; i < k; i++) { //понятно что у байта максимум //256 значений int[] c = new int [256]; //подсчитываю количество элементов //в массиве соответствующий каждому //байту как и в сортировке подсчетом for (int j = 0; j < n; j++) { c [digit (a[j], i) ] ++; } //модифицируем массив с //c[i] - номер элемента // следующего после i-го блока for (int j = 1; j < 256; j++) { c [j] += c [j - 1]; } //сдвигаем массив for(int j = n - 1; j > -1; j--)
{
b [--c [digit (a[j], i) ]] = a[j];
}
for(int j = 0; j < n; j++) { a[j] = b[j]; } } for(int i = 0; i < size; i++) { Console.Write(a[i]); Console.Write(' '); } } } }

Научиться программировать

  • на Delphi

  • на Java

  • на C++