转载：算法：计数排序CountingSort
转载：算法：计数排序CountingSort
文章链接：https://zhuanlan.zhihu.com/p/104111123
我们知道快速排序的时间复杂度期望值是O(nlogn)，其中O(logn)是利用了二分法进行远距离比较和交换元素的位置。如果不去做比较交换计算，有没有可能有一种算法，它的时间复杂度期望值能降低到O(n)线性时间呢？
我们可以有这样的思路，对于任何一个待排序数组的元素x，如果知道了待排序数组中有多少个元素比x小，就可以直接知道排序后x应该在什么位置上。例如，知道了待排序数组有5个元素比7小，就可以知道7在排序后是在第6个位置，对应的下标为5。
那什么知道数组中有多少个元素比x小呢？如果为了期望时间复杂度为线性时间，这种时候不可能去做比较计算。
一旦去做比较的方法就破坏了线性时间的期望。
我们可以有这样的思路，用空间去换时间，假设待排序数组a中n个数的取值范围是0到n，不妨设计一个长度为n+1的数组c，来统计数组a中每个元素出现的次数，存入到数组c中相应的位置。
这样就可以按照数组c出现的次数直接输出排序结果了。
但是如果期望保证待排序列的稳定性，相同的元素前后的顺序位置不期望被改变。可以将数组c从第2个元素开始，进行每一项和前一项的累加。
上面得出的结果意味着已经可以知道下标哪个元素在排序后放在哪个位置，减去了比较交换上的时间消耗。但是不确定出现相同次数的应该去哪个元素，例如7在第8个位置，8也在第8个位置，那第8个位置应该去哪个元素呢。
为了保证待排序列的稳定性，从数组a最后一个元素出发，根据数组c可以看到7是在第8个位置，可以设置要输出的数组b，长度和数组a一样。将7存入到数组b下标为7的位置上，数组c相应位置上的值需要减1，下一次再出现相同的元素则可以知道对应的位置，保证了元素之间的稳定性。
算法步骤：
找出待排序数组中的最大和最小的元素；
统计数组中每个值为x的元素出现的次数，存入到数组c中的下标为x的位置上；
从数组c中第2个元素开始，进行每一项和前一项的累加；
反向填充要输出的数组b，每放一个元素到数组b中，数组c相应位置上的值自算减法。
动画
算法动画视频地址 https://www.bilibili.com/video/av79587511/
[高清 720P] 计数排序.flv
Code
package cn.study.sort;
import java.util.Arrays;
public class CountingSort1 {
private static int[] countSort(int[] a){
int[] b = new int[a.length];
//求最大值
int max = a[0];
for(int i = 0; i < a.length; i++){
if(a[i] > max){
max = a[i];
}
}
//计数
int[] c = new int[max + 1];
for(int i = 0; i < a.length; i++){
c[a[i]]++;
}
// System.out.println("计数c：" + Arrays.toString(c));
//求计数和
for(int i = 1; i < max + 1; i++){
c[i] += c[i - 1];
}
// System.out.println("计数求和c：" + Arrays.toString(c));
//整理
for(int i = a.length - 1; i>= 0; i-- ){
// b[--c[a[i]]] = a[i];
b[c[a[i]] - 1] = a[i];
c[a[i]]--;
// System.out.println("c: " + Arrays.toString(c));
// System.out.println("b: " + Arrays.toString(b));
// System.out.println("=============");
}
return b;
}
public static void main(String[] args) {
int[] a = {7,7,3,5,9,3,1,5,7};
System.out.println("初始状态：" + Arrays.toString(a));
System.out.println(Arrays.toString(countSort(a)));//[1, 3, 3, 5, 5, 7, 7, 7, 9]
}
}
Result
初始状态 [7, 7, 3, 5, 9, 3, 1, 5, 7]计数c [0, 1, 0, 2, 0, 2, 0, 3, 0, 1]计数求和c [0, 1, 1, 3, 3, 5, 5, 8, 8, 9]c [0, 1, 1, 3, 3, 5, 5, 7, 8, 9]b [0, 0, 0, 0, 0, 0, 0, 7, 0]c [0, 1, 1, 3, 3, 4, 5, 7, 8, 9]b [0, 0, 0, 0, 5, 0, 0, 7, 0]c [0, 0, 1, 3, 3, 4, 5, 7, 8, 9]b [1, 0, 0, 0, 5, 0, 0, 7, 0]c [0, 0, 1, 2, 3, 4, 5, 7, 8, 9]b [1, 0, 3, 0, 5, 0, 0, 7, 0]c [0, 0, 1, 2, 3, 4, 5, 7, 8, 8]b [1, 0, 3, 0, 5, 0, 0, 7, 9]c [0, 0, 1, 2, 3, 3, 5, 7, 8, 8]b [1, 0, 3, 5, 5, 0, 0, 7, 9]c [0, 0, 1, 1, 3, 3, 5, 7, 8, 8]b [1, 3, 3, 5, 5, 0, 0, 7, 9]c [0, 0, 1, 1, 3, 3, 5, 6, 8, 8]b [1, 3, 3, 5, 5, 0, 7, 7, 9]c [0, 0, 1, 1, 3, 3, 5, 5, 8, 8]b [1, 3, 3, 5, 5, 7, 7, 7, 9][1, 3, 3, 5, 5, 7, 7, 7, 9]
优化：最小数值比较大的计数排序
如果考虑到待排序序列最小元素的数值比较大，比如[107, 107, 103, 105, 109, 103, 101, 105, 107]，最小元素的值是101，就浪费了数组c上0到100位置上的存储空间。所以就需要求最小值和最大值的差值来作为统计数组c的长度。
Code
package cn.study.sort;
import java.util.Arrays;
public class CountingSort2 {
public static int[] countSort2(int[] a){
int[] b = new int[a.length];
//求最大值、最小值
int max = a[0];
int min = a[0];
for(int i = 0; i < a.length; i++){
if(a[i] > max){
max = a[i];
}
if(a[i] < min){
min = a[i];
}
}
// System.out.println("max=" + max + ", min=" + min);
//计数
int[] c = new int[max - min + 1];
for(int i = 0; i < a.length; i++){
c[a[i] - min]++;
}
// System.out.println("计数c：" + Arrays.toString(c));
//求计数和
for(int i = 1; i < max - min + 1; i++){
c[i] += c[i - 1];
}
// System.out.println("计数求和c：" + Arrays.toString(c));
//整理
for(int i = a.length - 1; i>= 0; i-- ){
//b[--c[a[i]-min]] = a[i];
int j = a[i]-min;
c[j]--;
b[c[j]] = a[i];
// System.out.println("c: " + Arrays.toString(c));
// System.out.println("b: " + Arrays.toString(b));
// System.out.println("=============");
}
return b;
}
public static void main(String[] args) {
int[] a = {107, 107, 103, 105, 109, 103, 101, 105, 107};
System.out.println("初始状态：" + Arrays.toString(a));
System.out.println(Arrays.toString(countSort2(a)));//[101, 103, 103, 105, 105, 107, 107, 107, 109]
}
}
Result
初始状态 [107, 107, 103, 105, 109, 103, 101, 105, 107]计数c [1, 0, 2, 0, 2, 0, 3, 0, 1]计数求和c [1, 1, 3, 3, 5, 5, 8, 8, 9]c [1, 1, 3, 3, 5, 5, 7, 8, 9]b [0, 0, 0, 0, 0, 0, 0, 107, 0]c [1, 1, 3, 3, 4, 5, 7, 8, 9]b [0, 0, 0, 0, 105, 0, 0, 107, 0]c [0, 1, 3, 3, 4, 5, 7, 8, 9]b [101, 0, 0, 0, 105, 0, 0, 107, 0]c [0, 1, 2, 3, 4, 5, 7, 8, 9]b [101, 0, 103, 0, 105, 0, 0, 107, 0]c [0, 1, 2, 3, 4, 5, 7, 8, 8]b [101, 0, 103, 0, 105, 0, 0, 107, 109]c [0, 1, 2, 3, 3, 5, 7, 8, 8]b [101, 0, 103, 105, 105, 0, 0, 107, 109]c [0, 1, 1, 3, 3, 5, 7, 8, 8]b [101, 103, 103, 105, 105, 0, 0, 107, 109]c [0, 1, 1, 3, 3, 5, 6, 8, 8]b [101, 103, 103, 105, 105, 0, 107, 107, 109]c [0, 1, 1, 3, 3, 5, 5, 8, 8]b [101, 103, 103, 105, 105, 107, 107, 107, 109][101, 103, 103, 105, 105, 107, 107, 107, 109]
优化：元素大小跨度很大的计数排序
如果输入数组[7, 7, 1000005, 1000009, 1000003, 1000001, 1000005 ,1, 3]，最小值为1，最大值为1000009，数组的长度为9，最大值和最小值的差为1000008。这对上面的优化已经无效了。
我们可以利用数据挖掘对待排序列进行简单的数据归约，根据规约后映射的值把待排序列分治为比较均匀的子序列。下面进行计算：
7 : (7 - 1) / 1000008 * 9 = 0；7 : (7 - 1) / 1000008 * 9 = 0；1000005 : (1000005 - 1) / 1000008 * 9 = 8；1000009 : (1000009 - 1) / 1000008 * 9 = 9；1000003 : (1000006 - 1) / 1000008 * 9 = 8；1000001 : (1000001 - 1) / 1000008 * 9 = 8；1000005 : (1000005 - 1) / 1000008 * 9 = 8；1 : (1 - 1) / 1000008 * 9 = 0；3 : (3 - 1) / 1000008 * 9 = 0；
进而把计算结果按照得到的映射值划分为多个子序列：
0 : [7, 7, 1, 3]；8 : [1000005, 1000003, 1000001, 1000005]；9 : [1000009]；
然后在分别进行计数排序，最后合并。
Code：归约化
Code：小规模化的计数排序
package cn.study.sort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class CountingSort3 {
public static void countSort3(int[] a) {
//求最大值、最小值
int max = a[0];
int min = a[0];
for(int i = 0; i < a.length; i++){
if(a[i] > max){
max = a[i];
}
if(a[i] < min){
min = a[i];
}
}
//规约
HashMap<Integer,ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i = 0; i < a.length; i++){
int index = (int)((float)(a[i] - min) / (max - min) * a.length);//先把(a[i] - min)强制转换为float型。最后把整个计算结果强制转换为int型。
if(!map.containsKey(index)){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(a[i]);
map.put(index, list);
}else{
map.get(index).add(a[i]);
}
}
//计数排序
int start = 0;
int end = -1;
int index = 0;
Set<Integer> keySet = map.keySet();
Iterator<Integer> it = keySet.iterator();
while(it.hasNext()){
start = end + 1;
Iterator<Integer> itVal = map.get(it.next()).iterator();
while(itVal.hasNext()){
end++;
a[index++] = itVal.next();
}
//子序列的计数排序
int[] b = countingSort2(a, start, end);
int j = 0;
for(int i = start; i <= end; i++){
a[i] = b[j++];
}
}
}
//小规模化的计数排序
public static int[] countingSort2(int[] a, int start, int end) {
// System.out.println("数组b：start和end下标：" + start + ", " + end);
if(a.length < 2){return a;}
int[] b = new int[a.length];
//求最大值、最小值
int max = a[start];
int min = a[start];
for(int i = start; i <= end; i++){
if(a[i] > max){max = a[i];}
if(a[i] < min){min = a[i];}
}
//计数
int[] c = new int[max - min + 1];
for(int i = start; i <= end; i++){c[a[i] - min]++;}
// System.out.println("计数c：" + Arrays.toString(c));
//求计数和
for(int i = 1; i < c.length; i++){c[i] += c[i - 1];}
// System.out.println("计数求和c：" + Arrays.toString(c));
//整理
for(int i = end; i >= start; i--){
//b[--c[a[i] - min]] = a[i];
int j = a[i] - min;
c[j]--;
b[c[j]] = a[i];
// System.out.println("c: " + Arrays.toString(c));
// System.out.println("b: " + Arrays.toString(b));
}
return b;
}
public static void main(String[] args) {
int[] a = {7,7,1000005,1000009,1000003,1000001,1000005,1,3};
// System.out.println("初始状态：" + Arrays.toString(a));
countSort3(a);
System.out.println(Arrays.toString(a));
}
}
Result
初始状态 [7, 7, 1000005, 1000009, 1000003, 1000001, 1000005, 1, 3]数组b start和end下标 0 3计数c [1, 0, 1, 0, 0, 0, 2]计数求和c [1, 1, 2, 2, 2, 2, 4]c [1, 1, 1, 2, 2, 2, 4]b [0, 3, 0, 0, 0, 0, 0, 0, 0]c [0, 1, 1, 2, 2, 2, 4]b [1, 3, 0, 0, 0, 0, 0, 0, 0]c [0, 1, 1, 2, 2, 2, 3]b [1, 3, 0, 7, 0, 0, 0, 0, 0]c [0, 1, 1, 2, 2, 2, 2]b [1, 3, 7, 7, 0, 0, 0, 0, 0]数组b start和end下标 4 7计数c [1, 0, 1, 0, 2]计数求和c [1, 1, 2, 2, 4]c [1, 1, 2, 2, 3]b [0, 0, 0, 1000005, 0, 0, 0, 0, 0]c [0, 1, 2, 2, 3]b [1000001, 0, 0, 1000005, 0, 0, 0, 0, 0]c [0, 1, 1, 2, 3]b [1000001, 1000003, 0, 1000005, 0, 0, 0, 0, 0]c [0, 1, 1, 2, 2]b [1000001, 1000003, 1000005, 1000005, 0, 0, 0, 0, 0]数组b start和end下标 8 8计数c [1]计数求和c [1]c [0]b [1000009, 0, 0, 0, 0, 0, 0, 0, 0][1, 3, 7, 7, 1000001, 1000003, 1000005, 1000005, 1000009]
计数排序的局限性
计数排序只能用于非负整数、序列相对比较密集的算法，如果符合这两个条件，而且不考虑空间复杂度，使用计数排序确实非常不错的算法。如果不符合这两个条件，也有相应的方法能够去解决。
如果有负整数，可以加上一个固定的常数使得待排序列的最小值为0；如果待排序列有多个小数，有一个小数已经低到0.000001，可以乘以倍数成正整数，然后进行归约化和分治为多个比较均匀的子序列；如果这两个情况都有的话也可以结合进行。不过代码量确实不如比较排序类的简单。