一句话︰用辅助数组对数组中出现的数字计数，元素转下标，下标转元素
假设元素均大于等于0，依次扫描原数组，将元素值k记录在辅助数组的k位上
思路：开辟新的空间，空间大小为max(source)扫描source，将value作为辅助空间的下标，用辅助空间的改位置元素记录value的个数。如：9 7 5 3 1 ，helper=arr(10)。一次扫描，value为9，将helper[9]++，value为7，将helper[7]++……
如此这般之后，我们遍历helper，如果该位（index）的值为0，说明index不曾在source中出现
如果该位（index)的值为1，说明index在source中出现了1次，为2自然是出现了2次
遍历helper就能将source修复为升序排列
时间复杂度： 扫描一次source，扫描一次helper，复杂度为O(N+k)
空间复杂度：辅助空间k，k=maxOf(source)
非原址排序
稳定性：相同元素不会出现交叉，非原址都是拷来拷去
如果要优化一下空间，可以求minOf(source)，helper的长度位max-min+1，这样能短点
计数有缺陷，数据较为密集或范围较小时，适用。
代码实现 public static void countSort(int[] source) { int max = Integer.MIN_VALUE; for (int i = 0; i < source.length; i++) { max = Math.max(max, source[i]); } int[] helper = new int[max + 1]; for (int e : source) { helper[e]++; } int current = 0; //数据回填的下标 for (int i = 1; i < helper.length; i++) { while (helper[i] > 0) { source[current++] = i; helper[i]--; } } } 桶排序 概念工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
最后按照数组下标遍历链表即可
桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。
但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
时间复杂度： O(N+C)，其中C=N*(logN-logM)
空间复杂度：N+M，M为桶的个数
非原址排序
稳定性：稳定
桶排序假设数据会均匀入桶，在这个前提下，桶排序很快！
代码实现 // 根据桶的个数来确定hash函数，这份代码适合桶的个数等于数组长度 private static int hash(int element, int max, int length) { //哈希规则 return (element * length) / (max + 1); } private void sort(int[] arr) { int length = arr.length; LinkedNode[] bucket = new LinkedNode[length]; // 桶的个数=length int max = maxOf(arr);// 求max // 入桶 for (int i = 0; i < length; i++) { int value = arr[i];//扫描每个元素 int hash = hash( arr[i], max, length ); // 桶的下标 if (bucket[hash] == null) { bucket[hash] = new LinkedNode( value ); // 初始化链表表头 } else { insertInto( value, bucket[hash], bucket, hash ); // 插入链表 } } private int maxOf(int[] arr){ //求数组最大元素 int max = Integer.MIN_VALUE; for(int num: arr){ max = Math.max(max,num); } return max; } int k = 0; // 记录数组下标 //出桶，回填arr for (LinkedNode node : bucket) { if (node != null) { while (node != null) { arr[k++] = node.value; node = node.next; } } } } private void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) { LinkedNode newNode = new LinkedNode( value ); //小于头节点，放在头上 if (value <= head.value) { newNode.next = head; // 替换头节点 bucket[hash] = newNode; return; } /*往后找第一个比当前值大的节点，放在这个节点的前面*/ LinkedNode p = head; LinkedNode pre = p; while (p != null && value > p.value) { pre = p; p = p.next; } if (p == null) { // 跑到末尾了 pre.next = newNode; } else { // 插入pre和p之间 pre.next = newNode; newNode.next = p; } } 基数排序 概念