[url]http://www.ahhf45.com/info/Data_Structures_and_Algorithms/algorithm/commonalg/sort/internal_sorting/bin_sort/bin_sort.htm
[/url]
平均情况下桶排序以线性时间运行。像计数排序一样,桶排序也对输入作了某种假设, 因而运行得很快。具体来说,计数排序假设输入是由一个小范围内的整数构成,而桶排序则 假设输入由一个随机过程产生,该过程将元素一致地分布在区间[0,1)上。
桶排序的思想就是把区间[0,1)划分成n个相同大小的子区间,或称桶,然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0,1)上,所以一般不会有很多数落在 一个桶中的情况。为得到结果,先对各个桶中的数进行排序,然后按次序把各桶中的元素列 出来即可。
在桶排序算法的代码中,假设输入是个含n个元素的数组A,且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶,并假设可以用某种机制来维护这些表。
桶排序的算法如下,其中floor(x)是地板函数,表示不超过x的最大整数。
procedure Bin_Sort(var A:List);
begin
n:=length(A);
for i:=1 to n do
将A[i]插到表B[floor(n*A[i])]中;
for i:=0 to n-1 do
用插入排序对表B[i]进行排序;
将表B[0],B[1],...,B[n-1]按顺序合并;
end;
http://hxraid.iteye.com/blog/647759
从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的排序算法时间复杂度的一个下界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),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。
其实我个人还有一个感受:在查找算法中,基于比较的查找算法最好的时间复杂度也是O(logN)。比如折半查找、平衡二叉树、红黑树等。但是Hash表却有O(C)线性级别的查找效率(不冲突情况下查找效率达到O(1))。大家好好体会一下:Hash表的思想和桶排序是不是有一曲同工之妙呢?
桶排序在海量数据中的应用
一年的全国高考考生人数为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亿个桶显然是不可能的。所以桶排序有其局限性,适合元素值集合并不大的情况。
分享到:
相关推荐
桶式排序法桶式排序法桶式排序法桶式排序法
数组应用之桶排序课件,用于信息学奥赛基础算法上课应用。课件内容讲解了桶排序的基本思想,问题应用,知识扩展及多维桶等。
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
桶排序算法是常见排序里最快的一种,比快排还要快…可扩展。iOS版的桶排序算法,欢迎大家学习,交流~
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
自己看书时写的排序算法:桶排序 CPP文件
详解Java常用排序算法-桶排序
自己实现的各种排序算法,多多指教,包括归并、插入、冒泡 、希尔、快速、桶排序。
对桶排序算法的基本实现...然后在一定范围内对桶排序和快速排序进行了比较
桶排序算法,适用于开发过程中提供一个排序算法。提高开发效率!
经典的桶排序算法实现,在vs2008上调试通过。 算法介绍: 假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数基本思想将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n), [1/n, 2/n)...
插入排序 并归排序 桶排序 快速排序这些算法书上的经典算法,给出了算法过程,可供测试实际运行效率或者学习算法本身
用java语言实现冒泡排序、插入排序、堆排序、快速排序、归并排序、希尔排序、桶排序,并且对各种排序算法进行性能的比较。
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引
本算法通过桶排序对一个随机数组进行排序,编程语言:C++。
但桶排序并不是比较排序,他不受到O(n log n)下限的影响。 原理 设置一个定量的数组当作空桶子。 寻访序列,并且把项目一个一个放到对应的桶子去。 对每个不是空的桶子进行排序。 从不是空的桶子里把项目再放回原来...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。