目录
一.桶排序：
二.计数排序：
三.基数排序：
一.桶排序：1、算法原理：
桶排序的核心思想是将要排序的数据分成几个规则的桶，对每个桶中的数据分别进行排序。 将桶重新排序后，按顺序取出各桶的数据，顺序就整齐了。
2、图片演示：
3、桶排序的时间复杂度为O(n)：
如果有n个要排序的数据，请将它们均匀地分成m个桶。 每个桶有k=n/m个要素。 在每个桶内使用合并排序，将时间复杂度设为o(k*logk )。 由于m个桶排序的时间复杂度为o(m*k*logk )，k=n/m，因此整个桶排序的时间复杂度为o ) n*log ) n/m )。 当桶的数量m接近数据的数量n时，log(n/m为非常小的常数，其中桶排序的时间复杂度接近o[n]。
因此，桶排序的时间复杂度取决于对各桶之间的数据进行排序的时间复杂度。 桶分割越小，各桶之间的数据越少，排序所需的时间也越少，但相应地空间消耗量会增加。
4、桶排序的使用条件和适用场景：
对要排序的数据的桶排序要求非常严格。 使用条件如下。
)首先，要排序的数据可以简单地分成m个桶，并且桶和桶之间必须有天然大小的顺序。 这样对每个桶中的数据进行排序后，就不需要对桶和桶之间的数据进行排序了。
)2)然后，每个桶之间的数据分布相对均匀。 如果数据被桶分隔后，桶中的数据非常多、非常少、不平均，则桶中数据排序的时间复杂度不是常数级别。 在极端情况下，如果所有数据都被分割到桶中，则会退化为o(nlogn )排序算法。
因此，桶排序适合外部排序。 外部排序是指数据存储在外部磁盘上，数据量大，内存有限，无法将数据全部加载到内存中。
5、应用案例：
)1)需求说明：有10GB的订单数据，需要按订单金额(假设金额都是正整数)排序，但内存有限为几百MB。
)2)解决方案：
扫描单据，查看订单金额所在的数据范围，如1元-10万元，分成100个桶。
第一桶装的是金额1-1000元以内的订单，第二桶装的是1001-2000元以内的订单，依次类推。
每个桶对应一个文件，按照金额范围的大小顺序进行编号(00、01、02、…、99 )。
将100个小文件按顺序放入内存并进行排序。
对所有文件进行排序后，按照文件编号从小文件开始依次读取小文件，然后写入大文件即可。
注意：如果单个文件不能全部加载到内存中，对该文件继续按前面的思路处理即可。
二、计数顺序：1、算法原理：
计数排序可以看成是桶排序的一种特殊情况，只是桶的大小粒度不一样如果要排序的n个数据不在太大的范围内，例如最大值为k，则可以将数据分成k个桶。 每个时段中的数据值相同，从而节省了在时段中排序的时间。
2、适用场景：
计数排序只能用于数据范围不大的场景。 如果数据范围k比要排序的数据n大很多，则不适合计数排序。 此外，计数排序只能对非负整数进行排序。 如果要排序的数据是其他类型，请将其转换为非负整数，而不改变相对大小。
3、动图演示：
4、算法描述：
(1)在要排序的数组中找到最大和最小元素；
)2)数数组中各值为I的要素出现的次数，并存放在数组c的第I项中；
3 )累计所有计数)从c的第一个元素开始，将每个项目与前一个项目相加)；
(4)将目标数组反向嵌入)各要素I配置在新数组的c )项中，每次配置要素时将c ) I )减1。
5、应用案例：
(1) ) ) )。
假设只有8个考生分数在0-5分之间，成绩存于数组A[8] = [2，5，3，0，2，3，0，3]。使用大小为6的数组C[6]表示桶，下标对应分数，即0，1，2，3，4，5。
C[6]存储的是考生人数，只需遍历一边考生分数，就可以得到C[6] = [2，0，2，3，0，1]。
对C[6]数组顺序求和则C[6]=[2，2，4，7，7，8]，C[k]存储的是小于等于分数k的考生个数。
（2）数组R[8] = [0，0，2，2，3，3，3，5]存储考生名次。那么如何得到R[8]的呢？
从后到前依次扫描数组A，比如扫描到3时，可以从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R的第7个元素（也就是数组R中下标为6的位置）。当3放入数组R后，小于等于3的元素就剩下6个了，相应的C[3]要减1变成6。
以此类推，当扫描到第二个分数为3的考生时，就会把它放入数组R中第6个元素的位置（也就是下标为5的位置）。当扫描完数组A后，数组R内的数据就是按照分数从小到大排列的了。
6、Java代码实现：
public class CountingSort { public void countingSort(int[] a){int len = a.length;if(len<=1) return;//1、查找数组中数据的范围int max = a[0];for(int i=1;i<len;i++){if(max<a[i]) max=a[i];}//2、申请一个数组cint[] c = new int[max+1]; //3、遍历数组，计算每个元素的个数，放入c中。for(int i=0;i<len;i++)c[a[i]]++;//4、依次累加for(int i=1;i<=max;i++)c[i]=c[i-1]+c[i];//5、申请一个临时数组，存储排序后的结果，并反向填充。int[] r = new int[len];//计数排序的关键步骤，参照上图：for(int i=len-1;i>=0;i--){int index = c[a[i]]-1;r[index] = a[i];c[a[i]]--;}//6、将结果拷贝回原数组for(int i=0;i<len;i++)a[i]=r[i];}}
7、算法分析：
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
三、基数排序：
1、算法原理：
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
2、使用条件：
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，因为基数要借助桶排序或者计数排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
3、动图演示：
（1）得数组中的最大数，并取得位数；
（2）arr为原始数组，从最低位开始取每个位组成radix数组；
（3）对radix进行计数排序（利用计数排序适用于小范围数的特点）；
4、算法分析：
（1）基数排序基于分别排序，分别收集，所以是稳定的。
（2）如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候，当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。
（3）基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。
5、应用案例：
需求：排序10万个手机号：
（1）比较两个手机号码a，b的大小，如果在前面几位中a已经比b大了，那后面几位就不用看了。但是这种排序不稳定。
（2）借助稳定排序算法的思想，可以先按照最后一位来排序手机号码，然后再按照倒数第二位来重新排序，以此类推，最后按照第一个位重新排序。
（3）经过11次排序后，手机号码就变为有序的了。
（4）每次排序有序数据范围较小，可以使用桶排序或计数排序来完成。