计数排序对具有不同键值的对象数进行计数。让我们看一个例子-
注意-以下代码也可以与负数一起使用。
import java.util.*; public class Demo{ static void count_sort(int[] arr){ int max_val = Arrays.stream(arr).max().getAsInt(); int min_val = Arrays.stream(arr).min().getAsInt(); int range = max_val - min_val + 1; int count[] = new int[range]; int result[] = new int[arr.length]; for (int i = 0; i < arr.length; i++){ count[arr[i] - min_val]++; } for (int i = 1; i < count.length; i++){ count[i] += count[i - 1]; } for (int i = arr.length - 1; i >= 0; i--){ result[count[arr[i] - min_val] - 1] = arr[i]; count[arr[i] - min_val]--; } for (int i = 0; i < arr.length; i++){ arr[i] = result[i]; } } static void printVal(int[] arr){ for (int i = 0; i < arr.length; i++){ System.out.print(arr[i] + " "); } System.out.println(""); } public static void main(String[] args){ int[] arr = {-5, 0, -3, 8, 34, 56, 89, -11, -95, -1, 10}; System.out.println("The array contains"); for (int i = 0; i < arr.length; i++){ System.out.print(arr[i] + " "); } System.out.println(); System.out.println("Implementing Counting Sort in Java results in : "); count_sort(arr); printVal(arr); } }
输出结果
The array contains -5 0 -3 8 34 56 89 -11 -95 -1 10 Implementing Counting Sort in Java results in : -95 -11 -5 -3 -1 0 8 10 34 56 89
名为Demo的类包含'count_sort'函数。在此,对数组进行迭代,并且计数值是增量。
接下来,对该计数数组进行迭代,并将上一个值分配给下一个值。再次迭代该数组,并将该数组的元素分配给结果数组,并减少count数组。然后,再次迭代该数组,并将结果数组中的元素分配给该数组。定义了打印功能,可在控制台上打印数据。main函数定义数组的元素,并在这些元素上调用count排序。