计数排序和桶排序
转载自：https://segmentfault.com/a/1190000014532984
计数排序
之前接触的选择、快排等算法，都是着眼于“怎么更快的调整元素位置”，以达到排序的目的。而计数排序则不然，设计思路可谓另辟蹊径！
思路
我们对15个10以内（0-10）的数字按从小到大的顺序进行排序，比如source = [6, 8, 6, 2, 2, 10, 8, 5, 1, 9, 6, 4, 0, 2, 7]，计数排序是这么运作的。
- 构建计数槽——一个索引（可视作编号）从0到10的int数组，数组中的元素都初始为0
- 遍历源数组source，以计数
既然叫计数槽（叫计数器也成，我更习惯把数组型的结构称之为“槽”），自然是计数用的。
1.遍历源数组，首先拿到第一个“元素 6”，将其放入对应的编号为 6 的槽。注意，这里不是将元素本身放入，只是进行计数！将“槽 6”的数字计为1，表示元素6已经有1个了。
2.继续遍历，第二个元素 8，放入编号为 8 的槽；第三个元素，值依然是6，计数再次+1后6号槽的数字变为2（表示元素6已经有2个了）……
遍历全部数字完成计数，其实翻译成文字就是source = [6, 8, 6, 2, 2, 10, 8, 5, 1, 9, 6, 4, 0, 2, 7]数组中，有1个“元素0”，1个“元素1”，3个“元素2”，0个“元素3”,1个“元素4”，1个“元素5”，3个“元素6”，1个“元素7”，2个“元素8”，1个“元素9”，1个“元素10”。
- 出槽：按指定顺序（从小到大）列出数字
可以看到，图中的虚线框中的数字已经是最终结果了！
代码
按照上述思路编写代码：
1 import com.google.common.collect.Lists; 2 3 import java.util.LinkedList; 4 import java.util.Random; 5 6 /** 7 * @description: 计数排序 8 * @author: liuzijian 9 * @date: 2018-04-17 08:29 10 */ 11 public class CounterOrder { 12 int counterArr[] = new int[11]; //计数槽 13 14 LinkedList<Integer> fifeenNum = Lists.newLinkedList(); 15 16 /** 17 * 随机数初始化0-10的15个数字 18 */ 19 private void init(){ 20 Random random = new Random(); 21 for(int i=0;i<15;i++){ 22 fifeenNum.add(random.nextInt(11)); 23 } 24 System.out.println("source="+fifeenNum); 25 } 26 27 public CounterOrder(){ 28 init(); 29 } 30 31 /** 32 * 计数排序 33 */ 34 public LinkedList<Integer> doOrder(){ 35 // <<<<<<<<< 1.计数 36 for(int i:fifeenNum){ 37 int count = counterArr[i]; 38 count++; 39 counterArr[i] = count; 40 } 41 42 // <<<<<<<<< 2.出槽 43 LinkedList<Integer> resList = Lists.newLinkedList(); 44 for(int i=0,len=counterArr.length;i<len;i++){ 45 int count = counterArr[i]; 46 while (count>0){ 47 resList.add(i); 48 count--; 49 } 50 } 51 return resList; 52 } 53 54 public static void main(String[] args) { 55 CounterOrder counter = new CounterOrder(); 56 System.out.println("result is "+counter.doOrder()); 57 } 58 }
其实，这个demo可以说是计数排序的低配阉割版，雄壮健全版比这稍复杂些。容老夫卖个关子，桶排序部分会解释这里。
问题
先抛出一个问题，供大家思考：如果待排序的数字中存在负数，怎么处理？这个问题不难，比如对-10到10的数字进行排序，完全可以构建个“21位的计数槽”，不过每个槽负责计数的元素变成了“索引-10”，即槽0对应-10的计数，槽1对应-9的计数……以此类推，并且出槽的时候记得+10就是了！
计数排序真正的问题，或者说弊端有两个：
- 不擅长处理范围跨度很大的数字排序
这点很好理解，比如范围在-20000到20000，仅仅选10个数字（比如：{-20000,-726...,20000,826...}）进行排序，槽需要很大的说。
- 浮点型数字不好处理
浮点怎么处理？对于两位小数的浮点，可采用“先乘100后续再除100”的方式曲线救国，但这样很容易产生上面“槽大”的问题，比如小数位数多（试想2位整数4位小数的情况——31.4159）。
桶排序
桶排序能解决浮点数字的问题，至于“槽大”嘛，依然深受其害。
思路
桶排序与计数排序的思路多少有些类似，有数组[67, 29, 74, 52, 13, 16, 15, 59, 20, 61, 43, 38]整装待排，还是一如既往的从小到大好了。
- 桶划分：设定桶的元素范围（姑且定为 10），进行第一次遍历，以获取最大值、最小值和桶的个数
计数排序的代码demo，称其为低配阉割版的原因也在于此——我们硬性规定了0-10的槽。如果我们通过1次遍历，获取到最小值和最大值，假如min=3 max=6，那么是不是只用四个槽就能实现计数了？
- 入桶：依次将元素放入适合自己的桶中（按桶设定的数字范围）
线通过颜色、虚实等作区分了，但还是有些乱 - -！
总之，最后桶中的元素分布如下。
- 桶内排序
各个桶之间的元素已经排好序了（桶0的元素 < 桶1的元素），但是桶内的元素顺序依然混乱，比如桶3中的 52 43，接下来需要对每个桶中的元素进行排序。桶内元素的排序方式方法不限，快排、选择等等看心情……
示例中只有桶1和桶3需要排序（其实是每个桶都要做桶内排序，桶内排序的时机可以选择在“入桶”或“出桶”时）
- 元素出桶
没啥好说的，顺序拿出就好。
代码
桶排序代码如下：
1 import com.google.common.collect.Lists; 2 3 import java.util.LinkedList; 4 5 /** 6 * @description: 桶排序 7 * @author: liuzijian 8 * @date: 2018-04-18 14:06 9 */ 10 public class BucketSort { 11 int arr[] = {67, 29, 74, 52, 13, 16, 15, 59, 20, 61, 43, 38}; //待排序数组 12 13 public static void main(String[] args) { 14 BucketSort bucketSort = new BucketSort(); 15 LinkedList<Integer> res = bucketSort.doOrder(); 16 System.out.println(res); 17 } 18 19 /** 20 * @description: 桶排序 21 * @return: java.util.LinkedList<java.lang.Integer> 22 * @date: 2018/4/20 16:22 23 */ 24 public LinkedList<Integer> doOrder() { 25 InitParam initParam = firstLoop(); //首次遍历，获取最大值、最小值、桶个数等信息 26 27 LinkedList<Integer>[] bucket = new LinkedList[initParam.bucketNum]; //桶初始化 28 29 // <<<<<<< 入桶方法 >>>>>>> 30 for(int i:arr){ 31 int bucketIndex = (i-initParam.min)/elementNum; //计算元素归属于哪个桶 32 LinkedList<Integer> list = bucket[bucketIndex]; 33 if(list==null){ 34 list = new LinkedList<>(); 35 bucket[bucketIndex] = list; 36 } 37 38 //入桶的同时进行桶内排序 39 addBySort(i,list); 40 } 41 42 // <<<<<<< 出桶方法 >>>>>>> 43 LinkedList<Integer> resList = Lists.newLinkedList(); 44 for(LinkedList<Integer> bucketElement:bucket){ 45 if(bucketElement!=null && bucketElement.size()>0){ 46 resList.addAll(bucketElement); 47 } 48 } 49 return resList; 50 } 51 52 /** 53 * 按从小到大的顺序进行插入 54 * @param i 55 * @param list 56 */ 57 private void addBySort(int i,LinkedList<Integer> list){ 58 if(list.size()==0){ 59 list.add(i); 60 return; 61 } 62 63 int index = 0; 64 65 for(Integer ele:list){ 66 if(i>=ele){ 67 index++; 68 }else{ 69 break; 70 } 71 } 72 list.add(index,i); 73 } 74 75 final int elementNum = 10; 76 77 /** 78 * 封装参数 79 */ 80 class InitParam { 81 int min; //最小值 82 int max; //最大值 83 int bucketNum; //桶个数 84 85 public InitParam(int min, int max, int bucketNum) { 86 this.min = min; 87 this.max = max; 88 this.bucketNum = bucketNum; 89 } 90 } 91 92 /** 93 * @description: 第一次轮询，获取最大值、最小值和桶个数 94 * @return: void 95 * @date: 2018/4/18 14:18 96 */ 97 public InitParam firstLoop() { 98 int min = arr[0]; 99 int max = arr[0]; 100 for (int i : arr) { 101 if (i < min) { 102 min = i; 103 } 104 if (i > max) { 105 max = i; 106 } 107 } 108 int addition = (max - min) % elementNum == 0 ? 0 : 1; //如果有余数，桶个数+1 109 int bucketNum = (max - min) / elementNum + addition; 110 111 return new InitParam(min, max, bucketNum); 112 } 113 }
讨论
桶排序的关键在于桶划分和桶内排序算法的选择。
- 时间角度
每个桶负责的元素范围大，则桶的个数少；每个桶负责的元素范围小，则桶的个数多。打个比方，对范围在0-20000之间的数字进行排序，如果桶元素范围设置为10，则需要2000个桶；如果桶范围选择2000，则只需要10个桶。而不同的桶内排序算法，随着待排元素个数的增加，表现出的耗时增长幅度，也不尽相同。
- 空间角度
桶排序一种是比较耗空间的算法，尤其是我现在的这种实现方式——第一次遍历时，计算好了桶的个数，进而划分好桶。还以范围在0-20000的数字排序为例，如果只有5个数source={20000,371,372,370,0}(当然这么少的数字可能就直接选其它排序方式了)，依然保持每个桶的负责范围10，一次性初始化好的2000个桶，最后只会用到3个桶，剩下的1997个空桶的唯一作用就是浪费空间！那么是不是可以每拿到一个元素，算出它的桶编号后，在入桶时仅仅初始化这一个桶呢？这样对于上面的source数组，我最终只需要构建桶0、桶370和桶2000共3个桶！
空间优化版桶排序
去掉了入桶时的顺序插入方法，改为出桶时先计数排序再出桶。
直接上代码吧：
1 import com.google.common.collect.Lists; 2 import com.google.common.collect.Maps; 3 4 import java.util.Iterator; 5 import java.util.LinkedList; 6 import java.util.List; 7 import java.util.Map; 8 9 /** 10 * @description: 桶排序空间优化版 11 * @author: liuzijian 12 * @date: 2018-04-18 14:06 13 */ 14 public class BucketSortUpgrade { 15 int arr[] = {306, 20000, 304, 12, 768, 310, 303, 307}; //待排序数组 16 final int elementNum = 10; 17 int min; //最小值 18 int max; //最大值 19 int bucketNum; //桶个数 20 21 public static void main(String[] args) { 22 BucketSortUpgrade bucketSort = new BucketSortUpgrade(); 23 LinkedList<Integer> res = bucketSort.doOrder(); 24 System.out.println(res); 25 } 26 27 /** 28 * @description: 桶排序 29 * @return: java.util.LinkedList<java.lang.Integer> 30 * @date: 2018/4/20 16:22 31 */ 32 public LinkedList<Integer> doOrder() { 33 firstLoop(); //首次遍历，获取最大值、最小值、桶个数等信息 34 35 Map<Integer, LinkedList<Integer>> bucket = Maps.newTreeMap(); 36 37 // <<<<<<< 入桶方法 >>>>>>> 38 for (int i : arr) { 39 int bucketIndex = (i - min) / elementNum; //计算元素归属于哪个桶 40 LinkedList<Integer> list = bucket.get(bucketIndex); 41 if (list == null) { 42 list = new LinkedList<>(); 43 bucket.put(bucketIndex, list); 44 } 45 list.add(i); 46 } 47 48 // <<<<<<< 出桶方法 >>>>>>> 49 LinkedList<Integer> resList = Lists.newLinkedList(); 50 Iterator<Map.Entry<Integer, LinkedList<Integer>>> iterator = bucket.entrySet().iterator(); 51 int[] counter = new int[elementNum]; //计数器提到外面来，避免每次都重新分配计数器所需空间 52 while (iterator.hasNext()) { 53 Map.Entry<Integer, LinkedList<Integer>> element = iterator.next(); 54 if (element.getValue() != null && element.getValue().size() > 0) { 55 resList.addAll(outBucket(element,counter)); //计数排序方式出桶 56 iterator.remove(); //每个桶完成出桶操作后，就释放桶空间 57 } 58 } 59 return resList; 60 } 61 62 /** 63 * 计数排序方式出桶 64 * 65 * @param bucketElement 66 * @return 67 */ 68 private List<Integer> outBucket(Map.Entry<Integer, LinkedList<Integer>> bucketElement,int[] counter) { 69 Integer bucketNo = bucketElement.getKey(); 70 int bucketStart = bucketNo * elementNum + min; 71 72 for(int i=0;i<elementNum;i++){ 73 counter[i] = 0; 74 } 75 76 for (Integer i : bucketElement.getValue()) { 77 int count = counter[i - bucketStart]; 78 count++; 79 counter[i - bucketStart] = count; 80 } 81 82 LinkedList<Integer> resList = Lists.newLinkedList(); 83 for (int i = 0; i < elementNum; i++) { 84 int count = counter[i]; 85 if (count > 0) { 86 resList.add(bucketStart + i); 87 count--; 88 } 89 } 90 return resList; 91 } 92 93 94 /** 95 * @description: 第一次轮询，获取最大值、最小值和桶个数 96 * @author: liuzijian 97 * @return: void 98 * @date: 2018/4/18 14:18 99 */ 100 public void firstLoop() { 101 min = arr[0]; 102 max = arr[0]; 103 for (int i : arr) { 104 if (i < min) { 105 min = i; 106 } 107 if (i > max) { 108 max = i; 109 } 110 } 111 int addition = (max - min) % elementNum == 0 ? 0 : 1; //如果有余数，桶个数+1 112 bucketNum = (max - min) / elementNum + addition; 113 } 114 }