Рубрики

Java-программа для сортировки по Radix

Алгоритм сортировки по радиксу
1) Выполните следующие действия для каждой цифры i, где i изменяется от наименее значимой цифры до самой значимой цифры.
…………. a) Сортировать входной массив, используя сортировку с подсчетом (или любую устойчивую сортировку) по i / '-ому разряду.

Джава

// Radix-сортировка реализации Java

import java.io.*;

import java.util.*;

  

class Radix {

  

    // Полезная функция для получения максимального значения в arr []

    static int getMax(int arr[], int n)

    {

        int mx = arr[0];

        for (int i = 1; i < n; i++)

            if (arr[i] > mx)

                mx = arr[i];

        return mx;

    }

  

    // Функция для подсчета сортировки arr [] в соответствии с

    // цифра, представленная exp.

    static void countSort(int arr[], int n, int exp)

    {

        int output[] = new int[n]; // выходной массив

        int i;

        int count[] = new int[10];

        Arrays.fill(count,0);

  

        // Сохраняем количество вхождений в count []

        for (i = 0; i < n; i++)

            count[ (arr[i]/exp)%10 ]++;

  

        // Изменим count [i] так, чтобы count [i] теперь содержал

        // фактическая позиция этой цифры на выходе []

        for (i = 1; i < 10; i++)

            count[i] += count[i - 1];

  

        // Создаем выходной массив

        for (i = n - 1; i >= 0; i--)

        {

            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

            count[ (arr[i]/exp)%10 ]--;

        }

  

        // Копируем выходной массив в arr [], так что теперь arr []

        // содержит отсортированные номера по текущей цифре

        for (i = 0; i < n; i++)

            arr[i] = output[i];

    }

  

    // Основная функция для сортировки arr [] размера n, используя

    // Radix Sort

    static void radixsort(int arr[], int n)

    {

        // Находим максимальное число, чтобы узнать количество цифр

        int m = getMax(arr, n);

  

        // Делаем подсчет для каждой цифры. Обратите внимание, что вместо

        // номер проходной цифры, переданный опыт. опыт 10 ^ я

        // где я текущая цифра

        for (int exp = 1; m/exp > 0; exp *= 10)

            countSort(arr, n, exp);

    }

  

    // Вспомогательная функция для печати массива

    static void print(int arr[], int n)

    {

        for (int i=0; i<n; i++)

            System.out.print(arr[i]+" ");

    }

  

  

    / * Функция драйвера для проверки вышеуказанной функции * /

    public static void main (String[] args)

    {

        int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

        int n = arr.length;

        radixsort(arr, n);

        print(arr, n);

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

Пожалуйста, обратитесь к полной статье о Radix Sort для более подробной информации!

Рекомендуемые посты:

Java-программа для сортировки по Radix

0.00 (0%) 0 votes