集册 Java实例教程 基数排序的Java实现

基数排序的Java实现

欢马劈雪     最近更新时间:2020-01-02 10:19:05

399
提示:您可在线编辑运行本教程的实例 - 运行实例,去试试!
基数排序的Java实现

// 


public class Radix_Sort 

{/**来 自 n o w j a v a . c o m - 时  代  Java**/

    // Function implementing Radix Sort

    public static void radix_sort(int input[]) 

    {

        int i;

        int max = input[0]; // Maximum Element in input array

        int size = input.length;


        // Find the Maximum element in array

        for (i = 1; i < size; i++) /** NowJava.com - 时代Java 提供 **/

        {

            if (input[i] > max)

                max = input[i];

        }


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

        {

            Counting_Sort(input, size, exp); // Subroutine call to Counting_Sort

        }


    }


    // Counting_Sort

    public static void Counting_Sort(int input[], int size, int exp) 

    {

        int output[] = new int[size];

        int i;

        int count[] = new int[10];


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

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


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

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


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

        {

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

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

        }


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

            input[i] = output[i];

    }


    // Driver Function

    public static void main(String[] args) 
展开阅读全文