我们之前学到的排序方法都是进行比较来排序，那么有没有一种排序是无需比较呢？
答案显而易见是有的，那就是计数排序
存在数组 A{2,5,3,0,2,3,0,3}，使用计数排序进行排序
思路
统计元素出现次数（统计表）
出现次数| 2 | 0 | 2 | 3 | 0 |1|
-
元素 0 1 2 3 4 5
计算元素位置（索引表）
向前累加，目的是为了让统计数组存储的元素值，等于对应数的排序索引 位置| 2 | 2 | 4 | 7 | 7 |8|
-
元素 0 1 2 3 4 5
遍历原数组 A
创建一个新数组 B，用来存放已排好序的数组 A
接下来，我们对数组进行遍历
- A[0] = 2，2在索引表中对应位置为4，所以B[4-1] = B[3] = 2,索引表对应位置 -1,4成了3；
- A[1] = 5，5在索引表中对应位置为8，所以B[8-1] = B[7] = 5,索引表对应位置 -1,8成了7；
- A[2] = 3，3在索引表中对应位置为7，所以B[7-1] = B[6] = 3,索引表对应位置 -1,7成了6；
- 依次类推…
最后我们得到已排好序的数组 B[]，排序结束
注意事项
- 当原数组中的元素值比较大，我们是否还能直接根据索引来创建数组呢？
- 答案显示是不能的，因为会占用太多多余的空间。
我们只需要用到红色区域的元素。那么该如何解决呢？ - 我们可以求出数组的
最大值和最小值，然后创建差值长度的数组，arr[0] = arr[ arr[0] - min ]即可
- 答案显示是不能的，因为会占用太多多余的空间。
- 因为涉及数组较多，且索引
key不只是单纯的无意义索引，而是元素的值。而数组的value则是元素的出现次数或者是位置，一定要注意对应关系！
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Test {
public static void main(String[] args) {
//原数组
int[] arr = {92,95,97,90,92,94,90,98};
//创建一个新数组，用来存放排序之后的新数组
int[] arrSort= new int[arr.length];
//求出原数组最大值和最小值
int max = arr[0];
int min = arr[0];
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max){
max = arr[i];
}
if(arr[i] < min){
min = arr[i];
}
}
//最大值和最小值的差值
int d = max-min; // 5
int[] arrCount = new int[d+1]; //注意此处加一 （数组长度和数组索引差一，因为索引从 0 开始）
//遍历原数组，统计元素出现次数
for (int i = 0; i < arr.length; i++) {
arrCount[arr[i] - min]++; //数组索引从0开始，我们要加上min,这样的话数组 的所有 恰好是从 min ~ max
}
System.out.println(Arrays.toString(arrCount)); //[2, 0, 2, 3, 0, 1]
//向前相加，得到索引排序数组
for (int i = 1; i < arrCount.length; i++) {
arrCount[i] = arrCount[i] + arrCount[i-1];
}
System.out.println(Arrays.toString(arrCount)); //[2, 2, 4, 4, 5, 6, 6, 7, 8]
//根据索引排序数组分别取出元素，要注意索引分别对应的值
for (int i = 0; i < arr.length; i++) {
arrSort[arrCount[arr[i] - min] - 1] = arr[i];
arrCount[arr[i] - min]--;
}
System.out.println(Arrays.toString(arrSort)); //[90, 90, 92, 92, 94, 95, 97, 98]
}
}
更为清楚的解答：漫画：什么是计数排序？
笔记
