Code example of Java implementation of counting sort (CountingSort)

This article brings you code examples about Java implementation of counting sorting (CountingSort). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. help.

Counting sorting is a special type of bucket sorting.

When n data are to be sorted, if the range is not large, we can take the maximum value K and disperse the data in K buckets,

Each The data in the buckets are all the same (this saves the time of sorting in the buckets), and then they are taken out in sequence.

Of course, counting and sorting is simple to say, but it is difficult to understand in some places when writing.

For example, we now have 8 numbers: 2, 5, 3, 0, 2, 3, 0, 3. To sort them, we can first get its maximum value of 5, and then determine the range. 0-5,

We apply for a memory space of 0-5 to calculate the number of each number corresponding to each position.

The picture below shows the data of the memory space 0-5. We can see that 0 appears twice, 1 appears 0 times, 2 appears twice, 3 appears three times, and 4 appears. 0 times, 5 appeared once.

At the same time, we can also summarize some rules. For example, we now see the position c[2], 2 appears twice, and there are a total of 2 c[0] c[1] in front of 2. element, so c[2] corresponds to the positions of the two 2s in the original array, which are 2 and 3. We can draw the rule that the position of c[2] = c[0] c[1], and the following c[3] Position = c[2] c[1], we sum them sequentially like this: Then we scan the original array 2, 5, 3, 0, 2, 3, 0, 3. Every time we encounter a number, Substitute this number into the index of the c array to get the real index of the current element after sorting.

My Java implementation is as follows:

package com.structure.sort;
/**
 * @author zhangxingrui
 * @create 2019-01-30 13:45
 **/
public class CountingSort {
    public static void main(String[] args) {
        int[] numbers = {3, 9, 2, 1, 8, 7, 6, 10, 9};
        // 假设数组中存储的都是非负整数
        countingSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 计数排序
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(int[] numbers){
        int n = numbers.length;
        int maxNumber = numbers[0];
        for(int i = 1; i < n; ++i){
            if(numbers[i] > maxNumber)
                maxNumber = numbers[i];
        }
        int[] r = new int[n];
        int[] c = new int[maxNumber + 1];
        for(int i = 0; i < n; ++i){
            c[numbers[i]]++;
        }
        for(int i = 1; i <= maxNumber; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;
        }
        for(int i = 0; i < n; ++i){
            numbers[i] = r[i];
        }
    }
}

The key code:

for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;5         
            }

Retrieve the sorted index from the c array.

The above is the detailed content of Code example of Java implementation of counting sort (CountingSort). For more information, please follow other related articles on the PHP Chinese website!