十大经典排序(六)--计数排序及其优化
计数排序思路：
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。之后遍历额外开辟的空间，将存储的值按顺序倒回原数组即可
算法步骤：
花O(n)的时间扫描一下整个序列 A，获取最大值 max
开辟一块新的空间创建新的数组 B，长度为max+1
数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数
代码：
1private static void countSort(int arr[]) {
2 if (arr == null || arr.length == 0) {
3 return;
4 }
5 int max = arr[0];
6 //找最大值
7 for (int i = 1; i < arr.length; i++) {
8 if (arr[i] > max) {
9 max = arr[i];
10 }
11 }
12 //建立最大数组
13 int[] temp = new int[max + 1];
14 //填充计数
15 for (int anArr : arr) {
16 temp[anArr]++;
17 }
18 int index = 0;
19 //倒回原数组
20 for (int i = 0; i < temp.length; i++) {
21 while (temp[i] > 0) {
22 arr[index++] = i;
23 temp[i]--;
24 }
25 }
26 }
时间复杂度：O(n + k) 其中k是最大值
空间复杂度：O(k)
优化：
思路：上面实现有两个问题
不能排序负数
当数组中最小值和最大值都很大时，会浪费空间（0-min之间的空间没有利用）
针对这两个问题，咱们同时找出最大值和最小值，申请空间的大小为
max - min + 1，每个元素对应的计数位置则为array[i] - min，这样咱们就能将负数也计数起来，同时当min和max接近时且大于0时，能节省0~min之间的空间
代码
1private static void countSort(int arr[]) {
2 if (arr == null || arr.length == 0) {
3 return;
4 }
5 int min = arr[0];
6 int max = arr[0];
7 //同时计算最大值和最小值
8 for (int i = 1; i < arr.length; i++) {
9 if (arr[i] > max) {
10 max = arr[i];
11 } else if (arr[i] < min) {
12 min = arr[i];
13 }
14 }
15 int[] temp = new int[max - min + 1];
16 //将每个元素放入辅助数组，位置为 array[i] - min
17 for (int anArr : arr) {
18 temp[anArr - min]++;
19 }
20
21 int index = 0;
22 //倒回原数组
23 for (int i = 0; i < temp.length; i++) {
24 while (temp[i] > 0) {
25 arr[index++] = i + min;
26 temp[i]--;
27 }
28 }
29 }
时间复杂度：O(n + k) 其中k是最大值
空间复杂度：O(k)
题外话：计数排序必然会存在空间浪费，这样只是尽可能减少而已...
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
往期精彩推荐