How to implement counting sort algorithm using java

How to use Java to implement counting sorting algorithm

Counting sorting is a non-comparative sorting algorithm. Its main idea is to count the number of times each element appears in the array. , and then place the element in the correct position based on the number of times it appears. The time complexity of counting sort is O(n k), where n is the length of the sequence to be sorted, and k is the range of the largest element in the sequence to be sorted.

In Java, we can use the following code example to implement the counting sort algorithm:

public class CountingSort {
    public static void countingSort(int[] array) {
        int n = array.length;
        
        // 找到待排序序列中的最大值
        int max = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        // 创建一个计数数组，并初始化为0
        int[] count = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            count[i] = 0;
        }
        
        // 统计每个元素在待排序序列中出现的次数
        for (int i = 0; i < n; i++) {
            count[array[i]]++;
        }
        
        // 根据计数数组构建有序序列
        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                array[index] = i;
                index++;
                count[i]--;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] array = {9, 1, 5, 3, 7, 3, 8, 2, 6};
        
        System.out.println("排序前：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        countingSort(array);
        
        System.out.println("排序后：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

In the above code, we first find the maximum value in the sequence to be sorted, and then create a counting array, And count the occurrences of each element in the count array. Next, we construct an ordered sequence based on the count array. The specific operation is to place the elements in the count array into the sequence to be sorted according to the number of occurrences. Finally, by calling the countingSort method and printing the ordered sequence, we can see the results of the counting sort.

It should be noted that counting sorting has certain restrictions on the range of elements in the sequence to be sorted, and is only applicable to non-negative integer sequences. If there are negative numbers or elements of other data types in the sequence to be sorted, appropriate processing is required before the counting sort algorithm can be used.

The above is the detailed content of How to implement counting sort algorithm using java. For more information, please follow other related articles on the PHP Chinese website!