常用12大排序算法之十:桶排序算法-基数排序算法

2017-04-22 23:32 阅读 761 次 评论 0 条

1.桶排序的基本思想

桶排序的基本思想是将一个数据表分割成许多buckets,然后每个bucket各自排序,或用不同的排序算法,或者递归的使用bucket sort算法。也是典型的divide-and-conquer分而治之的策略。它是一个分布式的排序,介于MSD基数排序和LSD基数排序之间。

桶排序算法要求,数据的长度必须完全一样,程序过程要产生长度相同的数据

关于基数排序,可以参考《常用12大排序算法之九:基数排序(LSD+MSD)-桶子法排序》

 

2.桶排序的基本流程

(1)具体过程

建立一堆buckets;

遍历原始数组,并将数据放入到各自的buckets当中;

对非空的buckets进行排序;

按照顺序遍历这些buckets并放回到原始数组中即可构成排序后的数组。

桶排序

(2)代码实现过程

设置一个定量的数组当作空桶子;

寻访序列,并且把项目一个一个放到对应的桶子去;

对每个不是空的桶子进行排序;

从不是空的桶子里把项目再放回原来的序列中。

 

3.桶排序的复杂度

桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的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),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。

 

4.桶排序算法C语言源代码

 

5.桶排序算法C++源代码

 

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之十:桶排序算法-基数排序算法 | 算法君

发表评论


表情