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();}