Java排序之计数排序

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]