当输入的元素是n个0到k之间的整数时，它的运行时间是 O(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量额外内存空间。
稳定性：稳定
时间复杂度：最佳：O(n+k) 最差：O(n+k) 平均：O(n+k)
空间复杂度：O(k)
桶排序(Bucket Sort)桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行。
算法步骤设置一个BucketSize，作为每个桶所能放置多少个不同数值；
遍历输入数据，并且把数据依次映射到对应的桶里去；
对每个非空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
从非空桶里把排好序的数据拼接起来。
图解算法
JAVA
/** * Gets the maximum and minimum values in the array * @param arr * @return */ private static int[] getMinAndMax(List<Integer> arr) { int maxValue = arr.get(0); int minValue = arr.get(0); for (int i : arr) { if (i > maxValue) { maxValue = i; } else if (i < minValue) { minValue = i; } } return new int[] { minValue, maxValue }; } /** * Bucket Sort * @param arr * @return */ public static List<Integer> BucketSort(List<Integer> arr, int bucket_size) { if (arr.size() < 2 || bucket_size == 0) { return arr; } int[] extremum = getMinAndMax(arr); int minValue = extremum[0]; int maxValue = extremum[1]; int bucket_cnt = (maxValue - minValue) / bucket_size + 1; List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i < bucket_cnt; i++) { buckets.add(new ArrayList<Integer>()); } for (int element : arr) { int idx = (element - minValue) / bucket_size; buckets.get(idx).add(element); } for (int i = 0; i < buckets.size(); i++) { if (buckets.get(i).size() > 1) { buckets.set(i, sort(buckets.get(i), bucket_size / 2)); } } ArrayList<Integer> result = new ArrayList<>(); for (List<Integer> bucket : buckets) { for (int element : bucket) { result.add(element); } } return result; }Python
def BucketSort(arr, bucket_size): if len(arr) < 2 or bucket_size == 0: return arr minValue, maxValue = getMinAndMax(arr) bucket_cnt = (maxValue-minValue)//bucket_size+1 bucket = [[] for i in range(bucket_cnt)] for i in range(len(arr)): idx = (arr[i]-minValue) // bucket_size bucket[idx].append(arr[i]) for i in range(len(bucket)): if len(bucket[i]) > 1: # 递归使用桶排序，也可使用其它排序算法 bucket[i] = BucketSort(bucket[i], bucket_size//2) result = [] for i in range(len(bucket)): for j in range(len(bucket[i])): result.append(bucket[i][j]) return result def getMinAndMax(arr): maxValue = arr[0] minValue = arr[0] for i in range(len(arr)): if arr[i] > maxValue: maxValue = arr[i] elif arr[i] < minValue: minValue = arr[i] return minValue, maxValue 算法分析稳定性：稳定
时间复杂度：最佳：O(n+k) 最差：O(n²) 平均：O(n+k)
空间复杂度：O(k)
基数排序(Radix Sort)基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序，复杂度为O(n×k)，n为数组长度，k为数组中元素的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
算法步骤取得数组中的最大数，并取得位数，即为迭代次数N（例如：数组中最大数值为1000，则N=4）；
A为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
将radix依次赋值给原数组；
重复2~4步骤N次
图解算法