java数据结构与算法之桶排序实现方法详解-创新互联

本文实例讲述了java数据结构与算法之桶排序实现方法。分享给大家供大家参考，具体如下：

基本思想：

假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数。将区间[0, M)划分为n个大小相等的子区间（桶），将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n]

[桶——关键字]映射函数

bindex=f(key)   其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如下图所示：

对上图只要顺序输出每个B[i]中的数据就可以得到有序序列了。

算法核心代码如下：

/// 

/// 桶排序
///
///如果有重复的数字,则需要 List数组,这里举的例子没有重复的数字
/// 
/// 待排数组
/// 待排数组中的大数,如果可以提供的话
/// 
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();
}