计数排序的Java实现

欢马劈雪

工程师 (已认证)

原创分享签约作者

发表于实例源码

450

计数排序的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(String[] args)

{
/**代码未完, 请加载全部代码(NowJava.com).**/

​x
 
​
​
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(String[] args)
​
    {
/**代码未完, 请加载全部代码(NowJava.com).**/