计数排序和基数排序都是典型的桶排序算法，桶排序只是一种思想而不是一种算法，桶排序是不需要比较的排序。
1、计数排序
计数排序需要有3个数组存储数组：
(1)A：源数组
(2)ballot：记录小于或等于元素个数的数组
(3)bucket：最终排序后的数组
其中ballot的元素个数取决于A中元素个数的最大值。因为ballot是记录小于或等于A中某元素个数的，所以ballot最大也只可能为A元素的最大值。当然要max+1，因为我们记录的是与A中元素值相对应的元素个数，即范围为大于等于0，小于等于max。
此处以[1,2,3,5,2,3]数组为例，该数组组长度为6。
计数排序是通过计算待排序数组[1~n]中小于某个数组的元素个数，来得出最终排序的位置的。
此处通过画图解释（蓝色的为数组下标，黄色为数组值）：
源数组最大元素值为5，所以ballot数组长度为5+1。
代码如下：
public int[] countingSort(int[] A, int n) {
//存放排序结果
int[] bucket = new int[n];
//A数组最大值
int max = Integer.MIN_VALUE;
for(int k = 0;k<n;k++){
if(A[k]>max){
max = A[k];
}
}
//存放票数
int[] ballot = new int[max+1];
//存放值为i的元素个数
for (int i = 0; i < n; i++) {
ballot[A[i]]++;
}
//存放小于或等于j的元素个数
for(int j = 1;j<ballot.length;j++){
ballot[j] += ballot[j-1];
}
for(int p = n-1;p>=0;p--){
//需要下标减一，因为ballot个数包括了自身
bucket[ballot[A[p]]-1] = A[p];
//此处减一是为重复元素考虑
ballot[A[p]]--;
}
return bucket;
}
2、基数排序
基数排序分为LSD（Least Significant Digit First，从低位到高位）的基数排序与MSD(Most Significant Digital First，从高位到低位)的基数排序，LSD适用于位数小的数列，位数多的话，选MSD效率较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个"桶子"中建立"子桶"，将每个桶子中的数值按照下一数位的值分配到"子桶"中。在进行完最低位数的分配后再合并回单一的数组中。
代码如下（使用LSD）：
public int[] radixSort(int[] A, int n) { // 找出数组最大值 int max = Integer.MIN_VALUE; for (int k = 0; k < n; k++) { if (A[k] > max) { max = A[k]; } } // 数组中最大位数 int count = 0; while (max > 0) { max /= 10; count++; }
//建立一个集合，该集合包含10个队列 List<Queue<Integer>> list = new LinkedList<>(); // 建立10个队列作为桶（一位十进制的数范围在0~9之间） for (int p = 0; p < 10; p++) { Queue<Integer> queue = new LinkedList<>(); list.add(queue); } for (int i = 0; i < count; i++) { for (int j = 0; j < n; j++) { // 求出当前位数的值 int b = (A[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i)); //将当前元素值放入b号桶 list.get(b).add(A[j]); } int c = 0; //遍历10个队列（桶） for(int p = 0;p<10;p++){ //将桶元素取出，覆盖原数组 while(list.get(p).size()>0){ Queue<Integer> queue2 = list.get(p); A[c++] = queue2.poll(); } } } return A; }
