桶排序，计数排序 都是非基于比较的排序算法，在一定数据量下（O(k)>O(n*log(n))）快于任何基于比较的排序算法 这3个排序算法的通用性不是很高，我认为排序算法虽然实用性在实际生产中各有不同但是他们的思路是比较重要的。桶排序 计数排序 基数排序 都对要排序数组有点要求。

桶排序

桶排序号称是最快的排序方法，但是也是最耗费空间的排序方法。

• 场景： 有5个学生，满分5分 他们考试分数分别为 （2，2，1，5，4）需要按照分数升序排序

• 思路： 满分5分，我们需要6个桶 int[5]，桶的下边即为所有的分数 0~5,然后遍历每个学生的分数把数据塞入桶内，出现一次桶内的值加1。输出时遍历桶，桶内值是几就输出几次

• 优点： 只遍历一次数组，速度快简单

• 缺点： 1.对数据范围有依赖 2.会浪费空间 3.只能记录值不能记录键

桶排序还适用于外部排序，我们经常遇见一些面试题诸如
有一亿条数据，电脑内存只有128MB怎么给他们排序，这样的题就是说计算器内存不够用了不能全部load进内存该怎么处理

正确的方法是

1. 确认数据每一条的大小
2. 根据数据的大小合理分出若干桶范围比如 100w 放成一个桶记录文件数据范围在1-100W，这样的桶搞100个。
3. 遍历1亿条数据，写入这100个桶中
4. 每个桶中的数据在放出来 load 进内存，用快排排好序吐出到文件中去
5. 把排好序的桶合并成一个文件

计数排序

计数排序的思路和桶排序的差不多，优点是不用比较可以弥补桶排序的不能记录键的问题。缺点 1.对数据范围有依赖 2.会浪费空间

• 思路：

1. 准备用于计数的桶A
2. 把需要排序的字段放入桶A，记录出现次数
3. 准备桶B，根据桶A的情况统计数字出现的位置。
4. 桶B中的每一个桶里面的值放入小于等于桶键的个数
5. 用需要排序的数据 去遍历桶B得到的桶值就是这个数据放置的位置

• 步骤

1. 排序 2，5，3，0，2，3，0，3

桶A 键是排序数组的范围值， 值是出现的次数

2. 桶B 键是排序数组的范围值，值是小于等于键值的数值（桶A左值加当前位置）

3. 倒叙去遍历需要排序的数组，在桶B上面获取相应的所在位置。桶B的键是需要排序的值，值是排序值所在的位置