- 浏览: 198308 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
NIghtmare28:
太好用了, 谢谢
Create Local Cloudera Parcels Repo to Save Your ASS -
oyxccyj:
你好,请问下你如上的问题解决了吗?我现在也遇到同样的问题,网上 ...
Homework - HBase Shell, Java Client and MapReduce Job -
20131007:
用java描述算法?
基础数据结构和算法二:Selection sort -
ender35:
第二种实现仅能用于数组排序
计数排序(Counting Sort) -
fy616508150:
我想知道有括号参加运算怎么办
算24算法实现
文章来源:http://hxraid.iteye.com/blog/647759
原文中有基于CPP的实现,本文将CPP代码翻译为Java。原文写得很不错,复制过来做个笔记。
全依赖“比较”操作的排序算法时间复杂度的一个下界O(N*logN)。但确实存在更快的算法。这些算法并不是不用“比较”操作,也不是想办法将比较操作的次数减少到 logN。而是利用对待排数据的某些限定性假设 ,来避免绝大多数的“比较”操作。桶排序就是这样的原理。
桶排序的基本思想
假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ,将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ,那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。
[桶—关键字]映射函数
bindex=f(key) 其中,bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效,其关键在于这个映射函数,它必须做到:如果关键字k1<k2,那么f(k1)<=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然,映射函数的确定与数据本身的特点有很大的关系,我们下面举个例子:
假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶,然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序后得到如下图所示:
对上图只要顺序输出每个B[i]中的数据就可以得到有序序列了。
桶排序代价分析
桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的f(k)值的计算,其作用就相当于快排中划分,已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
对N个关键字进行桶排序的时间复杂度分为两个部分:
(1) 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N)。
(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序,其时间复杂度为 ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。
很显然,第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此,我们需要尽量做到下面两点:
(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中,这样每个桶就有[N/M]个数据量。
(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据,这样就完全避开了桶内数据的“比较”排序操作。 当然,做到这一点很不容易,数据量巨大的情况下,f(k)函数会使得桶集合的数量巨大,空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。
对于N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
总结: 桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。
桶排序在海量数据中的应用
一年的全国高考考生人数为500 万,分数使用标准分,最低100 ,最高900 ,没有小数,你把这500 万元素的数组排个序。
分析:对500W数据排序,如果基于比较的先进排序,平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现,这些数据都有特殊的条件: 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法:创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出,即可以得到一个有序的序列。而且可以很容易的得到100分有***人,501分有***人。
实际上,桶排序对数据的条件有特殊要求,如果上面的分数不是从100-900,而是从0-2亿,那么分配2亿个桶显然是不可能的。所以桶排序有其局限性,适合元素值集合并不大的情况。
import java.util.Random; public class BucketSort { public static void main(String... args) { //int raw[]={49, 38, 65, 97, 76, 13, 27, 49}; if (args.length < 1) { System.out.println("usage: java BucketSort number"); return; } Random rand = new Random(); int count = Integer.parseInt(args[0]); int[] raw = new int[count]; for (int i = 0; i < count; i++) { raw[i] = rand.nextInt(100); } BucketSort bs = new BucketSort(); bs.bucketSort(raw, raw.length, 10); } public void bucketSort(int[] keys, int size, int bucketSize) { Node[] bucketTable = new Node[bucketSize]; for (int i = 0; i < bucketSize; i++) { bucketTable[i] = new Node(0, null); } for (int j = 0; j < size; j++) { Node node = new Node(keys[j], null); // mapping function int index = keys[j] / 10; Node n = bucketTable[index]; if (n.getKey() == 0) { bucketTable[index].setNext(node); bucketTable[index].setKey(bucketTable[index].getKey() + 1); } else { while (n.getNext() != null && n.getNext().getKey() <= node.getKey()) { n = n.getNext(); } node.setNext(n.getNext()); n.setNext(node); bucketTable[index].setKey(bucketTable[index].getKey() + 1); } } for (int b = 0; b < bucketSize; b++) { for (Node n = bucketTable[b].getNext(); n != null; n = n.getNext()) { System.out.print(n.toString()); } } System.out.println(); } } class Node { private int key; private Node next; public Node(int key, Node next) { this.key = key; this.next = next; } public int getKey() { return this.key; } public void setKey(int key) { this.key = key; } public Node getNext() { return this.next; } public void setNext(Node next) { this.next = next; } public String toString() { return this.key + "\t"; } }
end.
发表评论
-
基础数据结构和算法十四:Directed Graphs
2013-12-15 22:40 1762In directed graphs, edges a ... -
基础数据结构和算法十三:Undirected Graphs (2)
2013-12-13 22:51 1018Design pattern for graph p ... -
基础数据结构和算法十三:Undirected Graphs
2013-12-13 20:15 1167A graph is a set of vertices ... -
基础数据结构和算法十二:Hash table
2013-12-02 22:06 990Search algorithms that use ... -
基础数据结构和算法十一:Red-black binary search tree
2013-12-01 12:12 1484The insertion algorithm fo ... -
基础数据结构和算法十:2-3 search tree
2013-11-30 11:07 1180Binary search tree works w ... -
基础数据结构和算法九:Binary Search Tree
2013-11-28 22:39 1621A binary search tree (BST) ... -
基础数据结构和算法八:Binary search
2013-11-28 21:21 1098Binary search needs an ordere ... -
基础数据结构和算法七:Priority queue & Heap sort
2013-11-27 19:47 2666Some important applications o ... -
基础算法七: Priority queue & Heap sort
2013-11-26 21:46 0Some important applications ... -
基础数据结构和算法六:Quick sort
2013-11-21 19:33 1194Quick sort is probably used m ... -
Inversions of an array
2013-11-20 22:28 0TODO -
基础数据结构和算法五:Merge sort
2013-11-20 21:44 1944One of mergesort’s most at ... -
基础数据结构和算法四:Shell sort
2013-11-20 19:11 1143Shellsort is a simple exte ... -
Comparing two sorting algorithms
2013-11-19 21:16 774Generally we compare algorith ... -
基础数据结构和算法三:Insertion Sort
2013-11-19 21:06 951As in selection sort, the ite ... -
基础数据结构和算法二:Selection sort
2013-11-19 20:57 1131One of the simplest sortin ... -
基础数据结构和算法一:UnionFind
2013-11-19 20:47 1238The problem that we consid ... -
Three-sum with linear time complexity
2013-09-14 10:08 0TODO package org.george.algor ... -
Blooming Filter in Hadoop
2013-07-27 22:49 0TODO
相关推荐
多趟桶式排序bucket sort。数据输入:有10个数,范围为0到999。 [root@lumotuwe] gcc cas.c -o cas [root@lumotuwe] ./cas 64 8 216 512 27 729 0 1 343 125
桶排序,顾名思义就是运用桶的思想来将数据放到相应的桶内,再将每一个桶内的数据进行排序,最后把所有桶内数据按照顺序取出来,得到的就是我们需要的有序数据,可以在线性时间O(n)内完成排序工作
经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - ...
桶排序算法是一种基于计数的排序算法,其基本思想是先扫描一遍待排序的序列,找出最大值和最小值,然后根据最大值和最小值确定桶的个数,并将每个元素分配到对应的桶中,最后将每个桶中的元素进行排序,然后依次输出...
MPI bucket排序代码 用于mpi联系 熟悉bucket排序
BucketSort为AlgorithmMan中的桶排序演示工具(这是可执行文件;需要.net 4.0支持;非源代码)。 原文:C#算法设计排序篇之10-桶排序(附带动画演示程序) 链接:...
桶排序是一种线性排序算法,这里我们来详解Bucket Sort桶排序算法及C++代码实现示例,需要的朋友可以参考下
桶排序的MPI实现。MPI implementation of bucket sort.
随机产生一定范围内的随机数,进行桶排序,然后二分查找任意个数的数。
主要介绍了C++桶排序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
JavaScript桶排序算法桶排序算法桶排序(Bucket sort)也称箱排序,是一个排序算法,工作的原理是将数组分到几个桶里,桶的数量可由排序数组最大值与
桶排序(Bucket Sort)是对基数排序的一个变种。在排序过程中没有用到计数数组,而是用不同的桶来暂时存储关键字。使用静态队列模拟桶,实现桶排序。
桶排序(Bucket Sort)是对基数排序的一个变种。在排序过程中没有用到计数数组,而是用不同的桶来暂时存储关键字。使用二维数组模拟桶。
桶排序(Bucket Sort) 环形排序(Circle Sort) 鸡尾酒排序(Cocktail Shaker Sort) 梳排序(Comb Sort) 计数排序(Counting Sort) 循环排序(Cycle Sort) 双重排序(Double Sort) 荷兰国旗排序(Dutch ...
桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳...
leetcode 和 oj leetcode 全站排名 2021-01-12 160 60695 ...桶排序bucket sort 堆排序 heap_sort 二分查找 69 744 540 278 852[Easy] 贪心法 455 [Medium]435 [Medium]452 [Medium]406 121 122 605
桶排序(Bucket Sort)的原理很简单,它是将数组分到有限数量的桶子里。 假设待排序的数组a中共有N个整数,并且已知数组a中数据的范围[0, MAX)。在桶排序时,创建容量为MAX的桶数组r,并将桶数组元素都初始化为0;将...
桶排序 在每个存储桶中使用 InsertionSort 的 BucketSort 算法的实现。 这个实现制作了 10 个范围相等的桶,然后将每个元素放入正确的桶中。 然后将元素放入桶中后,对每个桶运行 InsertionSort。 之后,将数据组合...