资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/【算】计数排序和桶排序

【算】计数排序和桶排序

Yangyang / 3347人阅读

摘要：计数排序之前接触的选择快排等算法，都是着眼于怎么更快的调整元素位置，以达到排序的目的。桶排序桶排序能解决浮点数字的问题，至于槽大嘛，依然深受其害。思路桶排序与计数排序的思路多少有些类似，有数组整装待排，还是一如既往的从小到大好了。

计数排序

之前接触的选择、快排等算法，都是着眼于“怎么更快的调整元素位置”，以达到排序的目的。而计数排序则不然，设计思路可谓另辟蹊径！

思路

我们对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. import java.util.LinkedList;
  3. import java.util.Random;
  4. /**
  5.  * @description: 计数排序
  6.  * @author: liuzijian
  7.  * @date: 2018-04-17 08:29
  8.  */
  9. public class CounterOrder {
  10.     int counterArr[] = new int[11]; //计数槽
  11.     LinkedList fifeenNum = Lists.newLinkedList();
  12.     /**
  13.      * 随机数初始化0-10的15个数字
  14.      */
  15.     private void init(){
  16.         Random random = new Random();
  17.         for(int i=0;i<15;i++){
  18.             fifeenNum.add(random.nextInt(11));
  19.         }
  20.         System.out.println("source="+fifeenNum);
  21.     }
  22.     public CounterOrder(){
  23.         init();
  24.     }
  25.     /**
  26.      * 计数排序
  27.      */
  28.     public LinkedList doOrder(){
  29.         //  <<<<<<<<<   1.计数
  30.         for(int i:fifeenNum){
  31.             int count = counterArr[i];
  32.             count++;
  33.             counterArr[i] = count;
  34.         }
  35.         // <<<<<<<<<   2.出槽
  36.         LinkedList resList = Lists.newLinkedList();
  37.         for(int i=0,len=counterArr.length;i0){
  38.                 resList.add(i);
  39.                 count--;
  40.             }
  41.         }
  42.         return resList;
  43.     }
  44.     public static void main(String[] args) {
  45.         CounterOrder counter = new CounterOrder();
  46.         System.out.println("result is "+counter.doOrder());
  47.     }
  48. }

其实，这个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. import java.util.LinkedList;
  3. /**
  4.  * @description: 桶排序
  5.  * @author: liuzijian
  6.  * @date: 2018-04-18 14:06
  7.  */
  8. public class BucketSort {
  9.     int arr[] = {67, 29, 74, 52, 13, 16, 15, 59, 20, 61, 43, 38};   //待排序数组
  10.     public static void main(String[] args) {
  11.         BucketSort bucketSort = new BucketSort();
  12.         LinkedList res = bucketSort.doOrder();
  13.         System.out.println(res);
  14.     }
  15.     /**
  16.      * @description: 桶排序
  17.      * @return: java.util.LinkedList
  18.      * @date: 2018/4/20 16:22
  19.      */
  20.     public LinkedList doOrder() {
  21.         InitParam initParam = firstLoop();  //首次遍历，获取最大值、最小值、桶个数等信息
  22.         LinkedList[] bucket = new LinkedList[initParam.bucketNum]; //桶初始化
  23.         // <<<<<<<  入桶方法 >>>>>>>
  24.         for(int i:arr){
  25.             int bucketIndex = (i-initParam.min)/elementNum; //计算元素归属于哪个桶
  26.             LinkedList list = bucket[bucketIndex];
  27.             if(list==null){
  28.                 list = new LinkedList<>();
  29.                 bucket[bucketIndex] = list;
  30.             }
  31.             //入桶的同时进行桶内排序
  32.             addBySort(i,list);
  33.         }
  34.         // <<<<<<<  出桶方法 >>>>>>>
  35.         LinkedList resList = Lists.newLinkedList();
  36.         for(LinkedList bucketElement:bucket){
  37.             if(bucketElement!=null && bucketElement.size()>0){
  38.                 resList.addAll(bucketElement);
  39.             }
  40.         }
  41.         return resList;
  42.     }
  43.     /**
  44.      * 按从小到大的顺序进行插入
  45.      * @param i
  46.      * @param list
  47.      */
  48.     private void addBySort(int i,LinkedList list){
  49.         if(list.size()==0){
  50.             list.add(i);
  51.             return;
  52.         }
  53.         int index = 0;
  54.         for(Integer ele:list){
  55.             if(i>=ele){
  56.                 index++;
  57.             }else{
  58.                 break;
  59.             }
  60.         }
  61.         list.add(index,i);
  62.     }
  63.     final int elementNum = 10;
  64.     /**
  65.      * 封装参数
  66.      */
  67.     class InitParam {
  68.         int min;    //最小值
  69.         int max;    //最大值
  70.         int bucketNum;  //桶个数
  71.         public InitParam(int min, int max, int bucketNum) {
  72.             this.min = min;
  73.             this.max = max;
  74.             this.bucketNum = bucketNum;
  75.         }
  76.     }
  77.     /**
  78.      * @description: 第一次轮询，获取最大值、最小值和桶个数
  79.      * @return: void
  80.      * @date: 2018/4/18 14:18
  81.      */
  82.     public InitParam firstLoop() {
  83.         int min = arr[0];
  84.         int max = arr[0];
  85.         for (int i : arr) {
  86.             if (i < min) {
  87.                 min = i;
  88.             }
  89.             if (i > max) {
  90.                 max = i;
  91.             }
  92.         }
  93.         int addition = (max - min) % elementNum == 0 ? 0 : 1;   //如果有余数，桶个数+1
  94.         int bucketNum = (max - min) / elementNum + addition;
  95.         return new InitParam(min, max, bucketNum);
  96.     }
  97. }
讨论

桶排序的关键在于桶划分和桶内排序算法的选择。

时间角度

每个桶负责的元素范围大，则桶的个数少；每个桶负责的元素范围小，则桶的个数多。打个比方，对范围在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. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.Map;
  7. /**
  8.  * @description: 桶排序空间优化版
  9.  * @author: liuzijian
  10.  * @date: 2018-04-18 14:06
  11.  */
  12. public class BucketSortUpgrade {
  13.     int arr[] = {306, 20000, 304, 12, 768, 310, 303, 307};   //待排序数组
  14.     final int elementNum = 10;
  15.     int min;    //最小值
  16.     int max;    //最大值
  17.     int bucketNum;  //桶个数
  18.     public static void main(String[] args) {
  19.         BucketSortUpgrade bucketSort = new BucketSortUpgrade();
  20.         LinkedList res = bucketSort.doOrder();
  21.         System.out.println(res);
  22.     }
  23.     /**
  24.      * @description: 桶排序
  25.      * @return: java.util.LinkedList
  26.      * @date: 2018/4/20 16:22
  27.      */
  28.     public LinkedList doOrder() {
  29.         firstLoop();  //首次遍历，获取最大值、最小值、桶个数等信息
  30.         Map> bucket = Maps.newTreeMap();
  31.         // <<<<<<<  入桶方法 >>>>>>>
  32.         for (int i : arr) {
  33.             int bucketIndex = (i - min) / elementNum; //计算元素归属于哪个桶
  34.             LinkedList list = bucket.get(bucketIndex);
  35.             if (list == null) {
  36.                 list = new LinkedList<>();
  37.                 bucket.put(bucketIndex, list);
  38.             }
  39.             list.add(i);
  40.         }
  41.         // <<<<<<<  出桶方法 >>>>>>>
  42.         LinkedList resList = Lists.newLinkedList();
  43.         Iterator>> iterator = bucket.entrySet().iterator();
  44.         int[] counter = new int[elementNum];    //计数器提到外面来，避免每次都重新分配计数器所需空间
  45.         while (iterator.hasNext()) {
  46.             Map.Entry> element = iterator.next();
  47.             if (element.getValue() != null && element.getValue().size() > 0) {
  48.                 resList.addAll(outBucket(element,counter));   //计数排序方式出桶
  49.                 iterator.remove();  //每个桶完成出桶操作后，就释放桶空间
  50.             }
  51.         }
  52.         return resList;
  53.     }
  54.     /**
  55.      * 计数排序方式出桶
  56.      *
  57.      * @param bucketElement
  58.      * @return
  59.      */
  60.     private List outBucket(Map.Entry> bucketElement,int[] counter) {
  61.         Integer bucketNo = bucketElement.getKey();
  62.         int bucketStart = bucketNo * elementNum + min;
  63.         for(int i=0;i resList = Lists.newLinkedList();
  64.         for (int i = 0; i < elementNum; i++) {
  65.             int count = counter[i];
  66.             if (count > 0) {
  67.                 resList.add(bucketStart + i);
  68.                 count--;
  69.             }
  70.         }
  71.         return resList;
  72.     }
  73.     /**
  74.      * @description: 第一次轮询，获取最大值、最小值和桶个数
  75.      * @author: liuzijian
  76.      * @return: void
  77.      * @date: 2018/4/18 14:18
  78.      */
  79.     public void firstLoop() {
  80.         min = arr[0];
  81.         max = arr[0];
  82.         for (int i : arr) {
  83.             if (i < min) {
  84.                 min = i;
  85.             }
  86.             if (i > max) {
  87.                 max = i;
  88.             }
  89.         }
  90.         int addition = (max - min) % elementNum == 0 ? 0 : 1;   //如果有余数，桶个数+1
  91.         bucketNum = (max - min) / elementNum + addition;
  92.     }
  93. }
GPU云服务器 云服务器 计数排序 堆排序排序c语言 字符串排序数组排序算法 排序比较

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69192.html

相关文章

  • 这或许是东半球讲十大排序算法最好的一篇文章

    摘要：希尔排序希尔排序这个名字，来源于它的发明者希尔，也称作缩小增量排序，是插入排序的一种更高效的改进版本。我们可以发现，当区间为的时候，它使用的排序方式就是插入排序。 冒泡排序 冒泡排序无疑是最为出名的排序算法之一，从序列的一端开始往另一端冒泡（你可以从左往右冒泡，也可以从右往左冒泡，看心情），依次比较相邻的两个数的大小（到底是比大还是比小也看你心情）。 showImg(https://s...

    wind3110991 评论0 收藏0

  • 排序算法总结

    摘要：如果对空间限制不大，可以使用基数排序等方法降低时间复杂度，这些线性时间排序法是利用了数据的特性达到最佳的效果。 内部排序 以下为基于比较的排序。 一、插入排序 直接插入排序 基本思想： 将元素插入到已经排好序的序列中。第一个元素已经是有序序列，然后比较外围的元素和序列的最后一个元素，判断是否需要插入，如果小，则插入。 时间复杂度：最优 O(n) 最差 O(n^2) 是否稳定：是 ...

    KoreyLee 评论0 收藏0

发表评论

登陆后可评论

0条评论

Yangyang

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<