[toc]

Count sorting

  • Counting sort applies to arrays with a small difference between the maximum and minimum values. If the minimum is 0 and the maximum is 100 million, then you need to create an array with a capacity of 100 million elements, which is very time complex

  • Take the array elements as the subscript of the temporary array, count the number of occurrences of each table, and finally iterate the temporary array sequentially from the index 0, the number of n output n times, and then sort well

  • Why max-min + 1? Because if you’re 90-100, Max + 1 and you want to create an array of size 101, that’s a waste of space, so we can optimize it, create the difference between the largest element and the smallest element, and increment it in minutes, and then just create an array of size 10, And then the output just needs the index subscript plus the min change

  • The time complexity is O(n+ K), and the space complexity is O(k). N is the size of the array to be sorted and k is the size of the temporary array. This sort is a stable sort, which is out-of-place because a temporary array needs to be created

  • Code implementation

    import java.util.Arrays;

/ * * *@Description: counting sort *@Author: LinZeLiang
 * @Date: the 2020-10-09 * /
public class CountSort {

    public static void main(String[] args) {
        int[] a = {9.8.7.6.5.4.3.2.1.0};

        countSort(a);

        System.out.println(Arrays.toString(a));
    }

    /** * count sort **@paramA Array to be sorted */
    private static void countSort(int[] a) {
        int min = a[0];
        int max = a[0];
        // Find the maximum and minimum values
        for (int i = 0; i < a.length; i++) {
            if (min > a[i]) {
                min = a[i];
            }
            if(max < a[i]) { max = a[i]; }}// Create a temporary count array
        // Determine the length of the array according to the maximum and minimum
        int[] arr = new int[max - min + 1];
        // Start counting
        for (int i = 0; i < a.length; i++) {
            arr[a[i] - min]++;
        }
        // Iterate over the array of statistics, replacing the original array
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i]; j++) { a[k++] = i + min; }}}}Copy the code