java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要介绍了 java 数据结构与算法之桶排序实现方法, 结合具体实例形式详细分析了桶排序的概念、原理、实现方法与相关操作技巧, 需要的朋友可以参考下
本文实例讲述了 java 数据结构与算法之桶排序实现方法。分享给大家供大家参考,具体如下:
基本思想:
假定输入是由一个随机过程产生的 [0, M) 区间上均匀分布的实数。将区间 [0, M) 划分为 n 个大小相等的子区间(桶),将 n 个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入 0 ≤A[1..n] <M 辅助数组 B[0..n-1]是一指针数组,指向桶(链表)。将 n 个记录分布到各个桶中去。如果有多于一个记录分到同一个桶中,需要进行桶内排序。最后依次把各个桶中的记录列出来记得到有序序列。
[桶——关键字] 映射函数
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] 中的数据就可以得到有序序列了。
算法核心代码如下:
- /// <summary>
- /// 桶排序
- ///
- ///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
- /// </summary>
- /// <param name="unsorted">待排数组</param>
- /// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</param>
- /// <returns></returns>
- static int[] bucket_sort(int[] unsorted, int maxNumber = 97)
- {
- int[] sorted = new int[maxNumber + 1];
- for (int i = 0; i < unsorted.Length; i++)
- {
- sorted[unsorted[i]] = unsorted[i];
- }
- return sorted;
- }
- static void Main(string[] args)
- {
- int[] x = {49、 38 、 35、 97 、 76、 73 、 27、 49 };
- var sorted = bucket_sort(x, 97);
- for (int i = 0; i < sorted.Length; i++)
- {
- if (sorted[i] > 0)
- Console.WriteLine(sorted[i]);
- }
- Console.ReadLine();
- }
桶排序代价分析
桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的 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),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。
即以下三点:
1. 桶排序是稳定的
2. 桶排序是常见排序里最快的一种, 比快排还要快… 大多数情况下
3. 桶排序非常快, 但是同时也非常耗空间, 基本上是最耗空间的一种排序算法
补充:在查找算法中,基于比较的查找算法最好的时间复杂度也是 O(logN)。比如折半查找、平衡二叉树、红黑树等。但是 Hash 表却有 O(C) 线性级别的查找效率 (不冲突情况下查找效率达到 O(1))。那么:Hash 表的思想和桶排序是不是有一曲同工之妙呢
实际上,桶排序对数据的条件有特殊要求,如果数组很大的话,那么分配几亿个桶显然是不可能的。所以桶排序有其局限性,适合元素值集合并不大的情况。
希望本文所述对大家 java 程序设计有所帮助。
来源: http://www.phperz.com/article/17/1228/357232.html