资讯专栏INFORMATION COLUMN

【算】计数排序和桶排序

Yangyang / 3214人阅读

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

计数排序

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

思路

我们对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”。

出槽:按指定顺序(从小到大)列出数字

可以看到,图中的虚线框中的数字已经是最终结果了!

代码

按照上述思路编写代码:

import com.google.common.collect.Lists;

import java.util.LinkedList;
import java.util.Random;

/**
 * @description: 计数排序
 * @author: liuzijian
 * @date: 2018-04-17 08:29
 */
public class CounterOrder {
    int counterArr[] = new int[11]; //计数槽

    LinkedList fifeenNum = Lists.newLinkedList();

    /**
     * 随机数初始化0-10的15个数字
     */
    private void init(){
        Random random = new Random();
        for(int i=0;i<15;i++){
            fifeenNum.add(random.nextInt(11));
        }
        System.out.println("source="+fifeenNum);
    }

    public CounterOrder(){
        init();
    }

    /**
     * 计数排序
     */
    public LinkedList doOrder(){
        //  <<<<<<<<<   1.计数
        for(int i:fifeenNum){
            int count = counterArr[i];
            count++;
            counterArr[i] = count;
        }

        // <<<<<<<<<   2.出槽
        LinkedList resList = Lists.newLinkedList();
        for(int i=0,len=counterArr.length;i0){
                resList.add(i);
                count--;
            }
        }
        return resList;
    }

    public static void main(String[] args) {
        CounterOrder counter = new CounterOrder();
        System.out.println("result is "+counter.doOrder());
    }
}

其实,这个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需要排序(其实是每个桶都要做桶内排序,桶内排序的时机可以选择在“入桶”或“出桶”时

元素出桶

没啥好说的,顺序拿出就好。

代码

桶排序代码如下:

import com.google.common.collect.Lists;

import java.util.LinkedList;

/**
 * @description: 桶排序
 * @author: liuzijian
 * @date: 2018-04-18 14:06
 */
public class BucketSort {
    int arr[] = {67, 29, 74, 52, 13, 16, 15, 59, 20, 61, 43, 38};   //待排序数组

    public static void main(String[] args) {
        BucketSort bucketSort = new BucketSort();
        LinkedList res = bucketSort.doOrder();
        System.out.println(res);
    }

    /**
     * @description: 桶排序
     * @return: java.util.LinkedList
     * @date: 2018/4/20 16:22
     */
    public LinkedList doOrder() {
        InitParam initParam = firstLoop();  //首次遍历,获取最大值、最小值、桶个数等信息

        LinkedList[] bucket = new LinkedList[initParam.bucketNum]; //桶初始化

        // <<<<<<<  入桶方法 >>>>>>>
        for(int i:arr){
            int bucketIndex = (i-initParam.min)/elementNum; //计算元素归属于哪个桶
            LinkedList list = bucket[bucketIndex];
            if(list==null){
                list = new LinkedList<>();
                bucket[bucketIndex] = list;
            }

            //入桶的同时进行桶内排序
            addBySort(i,list);
        }

        // <<<<<<<  出桶方法 >>>>>>>
        LinkedList resList = Lists.newLinkedList();
        for(LinkedList bucketElement:bucket){
            if(bucketElement!=null && bucketElement.size()>0){
                resList.addAll(bucketElement);
            }
        }
        return resList;
    }

    /**
     * 按从小到大的顺序进行插入
     * @param i
     * @param list
     */
    private void addBySort(int i,LinkedList list){
        if(list.size()==0){
            list.add(i);
            return;
        }

        int index = 0;

        for(Integer ele:list){
            if(i>=ele){
                index++;
            }else{
                break;
            }
        }
        list.add(index,i);
    }

    final int elementNum = 10;

    /**
     * 封装参数
     */
    class InitParam {
        int min;    //最小值
        int max;    //最大值
        int bucketNum;  //桶个数

        public InitParam(int min, int max, int bucketNum) {
            this.min = min;
            this.max = max;
            this.bucketNum = bucketNum;
        }
    }

    /**
     * @description: 第一次轮询,获取最大值、最小值和桶个数
     * @return: void
     * @date: 2018/4/18 14:18
     */
    public InitParam firstLoop() {
        int min = arr[0];
        int max = arr[0];
        for (int i : arr) {
            if (i < min) {
                min = i;
            }
            if (i > max) {
                max = i;
            }
        }
        int addition = (max - min) % elementNum == 0 ? 0 : 1;   //如果有余数,桶个数+1
        int bucketNum = (max - min) / elementNum + addition;

        return new InitParam(min, max, bucketNum);
    }
}
讨论

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

时间角度

每个桶负责的元素范围大,则桶的个数少;每个桶负责的元素范围小,则桶的个数多。打个比方,对范围在0-20000之间的数字进行排序,如果桶元素范围设置为10,则需要2000个桶;如果桶范围选择2000,则只需要10个桶。而不同的桶内排序算法,随着待排元素个数的增加,表现出的耗时增长幅度,也不尽相同。

空间角度

桶排序一种是比较耗空间的算法,尤其是我现在的这种实现方式——第一次遍历时,计算好了桶的个数,进而划分好桶。还以范围在0-20000的数字排序为例,如果只有5个数source={20000,371,372,370,0}(当然这么少的数字可能就直接选其它排序方式了),依然保持每个桶的负责范围10,一次性初始化好的2000个桶,最后只会用到3个桶,剩下的1997个空桶的唯一作用就是浪费空间!那么是不是可以每拿到一个元素,算出它的桶编号后,在入桶时仅仅初始化这一个桶呢?这样对于上面的source数组,我最终只需要构建桶0、桶370和桶2000共3个桶!

空间优化版桶排序

去掉了入桶时的顺序插入方法,改为出桶时先计数排序再出桶。
直接上代码吧:

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @description: 桶排序空间优化版
 * @author: liuzijian
 * @date: 2018-04-18 14:06
 */
public class BucketSortUpgrade {
    int arr[] = {306, 20000, 304, 12, 768, 310, 303, 307};   //待排序数组
    final int elementNum = 10;
    int min;    //最小值
    int max;    //最大值
    int bucketNum;  //桶个数

    public static void main(String[] args) {
        BucketSortUpgrade bucketSort = new BucketSortUpgrade();
        LinkedList res = bucketSort.doOrder();
        System.out.println(res);
    }

    /**
     * @description: 桶排序
     * @return: java.util.LinkedList
     * @date: 2018/4/20 16:22
     */
    public LinkedList doOrder() {
        firstLoop();  //首次遍历,获取最大值、最小值、桶个数等信息

        Map> bucket = Maps.newTreeMap();

        // <<<<<<<  入桶方法 >>>>>>>
        for (int i : arr) {
            int bucketIndex = (i - min) / elementNum; //计算元素归属于哪个桶
            LinkedList list = bucket.get(bucketIndex);
            if (list == null) {
                list = new LinkedList<>();
                bucket.put(bucketIndex, list);
            }
            list.add(i);
        }

        // <<<<<<<  出桶方法 >>>>>>>
        LinkedList resList = Lists.newLinkedList();
        Iterator>> iterator = bucket.entrySet().iterator();
        int[] counter = new int[elementNum];    //计数器提到外面来,避免每次都重新分配计数器所需空间
        while (iterator.hasNext()) {
            Map.Entry> element = iterator.next();
            if (element.getValue() != null && element.getValue().size() > 0) {
                resList.addAll(outBucket(element,counter));   //计数排序方式出桶
                iterator.remove();  //每个桶完成出桶操作后,就释放桶空间
            }
        }
        return resList;
    }

    /**
     * 计数排序方式出桶
     *
     * @param bucketElement
     * @return
     */
    private List outBucket(Map.Entry> bucketElement,int[] counter) {
        Integer bucketNo = bucketElement.getKey();
        int bucketStart = bucketNo * elementNum + min;

        for(int i=0;i resList = Lists.newLinkedList();
        for (int i = 0; i < elementNum; i++) {
            int count = counter[i];
            if (count > 0) {
                resList.add(bucketStart + i);
                count--;
            }
        }
        return resList;
    }


    /**
     * @description: 第一次轮询,获取最大值、最小值和桶个数
     * @author: liuzijian
     * @return: void
     * @date: 2018/4/18 14:18
     */
    public void firstLoop() {
        min = arr[0];
        max = arr[0];
        for (int i : arr) {
            if (i < min) {
                min = i;
            }
            if (i > max) {
                max = i;
            }
        }
        int addition = (max - min) % elementNum == 0 ? 0 : 1;   //如果有余数,桶个数+1
        bucketNum = (max - min) / elementNum + addition;
    }
}

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

转载请注明本文地址: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元查看
<