计数排序的Java实现

public class Counting_Sort {

    // Function that sort the given input

    public static void sort(int input[])/* 来 自 NowJava.com - 时  代  Java*/

    {

        int n = input.length;

        int output[] = new int[n]; // The output will have sorted input array


        int max = input[0];

        int min = input[0];


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

        {

            if(input[i] > max)
            /*来自 
             时 代      J a v a   公   众 号 - nowjava.com*/

                max = input[i]; // Maximum value in array

            else if(input[i] < min)

                min = input[i]; // Minimum value in array

        }


        int k = max - min + 1; // Size of count array

        int count_array[] = new int[k]; // Create a Count array


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

            count_array[input[i] - min]++; // Store count of each individual input value


        // Change count_array so that count_array now contains actual

        // position of input values in output array

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

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


        // Populate output array using count_array and input array

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

        {

            output[count_array[input[i] - min] - 1] = input[i];

            count_array[input[i] - min]--;

        }


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

            input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values

    }


    // Driver program to test above function

    public static void main(