计数排序

1. 计数排序思路

计数排序适用于有明确范围的数组，比如给定一个数组，且知道所有值得范围是[m,n]。这个时候可以使用一个n-m+1长度的数组，待排序的数组就可以散在这个数组上，数组的值就是当前值的个数，再经过一次遍历展开，得到的数组就有序了。

1. 新建一个长度为n-m+1的临时数组

2. 遍历待排序数组，它的值-m作为临时数组下角标，这个位置的值加1

3. 遍历结束，临时数组就存储了每个值得个数

4. 最后将它展开赋值给原数组

2. Java代码实现

package com.wangjun.arithmetic;

import java.util.Arrays;

public class SortCount {

    public static void main(String[] args) {
        //测试
        int[] arr = {1,4,6,7,5,4,3,2,1,4,5,10,9,10,3};
        sortCount(arr, 1, 10);
        System.out.println(Arrays.toString(arr));
    }

    //计数排序的初步实现，使用了多余的空间，可以尝试不使用多余的空间
    public static void sortCount(int[] arr, int m, int n) {
        int len = arr.length;
        int[] tem = new int[n - m + 1];
        for(int i = 0; i < len; i++) {
            tem[arr[i] - m] += 1;
        }
        for(int i = 0, index = 0; i < tem.length; i++) {
            int item = tem[i];
            while(item-- != 0) {
                arr[index++] = i + m;
            }
        }
    }

}

打印结果：

[1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10]