摘要:计数排序之前接触的选择快排等算法,都是着眼于怎么更快的调整元素位置,以达到排序的目的。桶排序桶排序能解决浮点数字的问题,至于槽大嘛,依然深受其害。思路桶排序与计数排序的思路多少有些类似,有数组整装待排,还是一如既往的从小到大好了。
计数排序
之前接触的选择、快排等算法,都是着眼于“怎么更快的调整元素位置”,以达到排序的目的。而计数排序则不然,设计思路可谓另辟蹊径!
思路我们对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]; //计数槽 LinkedListfifeenNum = 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;i 0){ 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(); LinkedListres = 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...
阅读 1715·2021-11-25 09:43
阅读 15099·2021-09-22 15:11
阅读 2605·2019-08-30 13:19
阅读 1982·2019-08-30 12:54
阅读 1801·2019-08-29 13:06
阅读 906·2019-08-26 14:07
阅读 1597·2019-08-26 10:47
阅读 3006·2019-08-26 10:41