首页 > 代码库 > 经典算法之排序问题（二）：桶排序、鸽巢排序
经典算法之排序问题（二）：桶排序、鸽巢排序
鸽巢排序：
鸽巢排序, 也被称作基数分类, 是一种时间复杂度为(Θ(n))且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法. 但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用.
当涉及到多个不相等的元素, 且将这些元素放在同一个"鸽巢"的时候, 算法的效率会有所降低.为了简便和保持鸽巢排序在适应不同的情况, 比如两个在同一个存储桶中结束的元素必然相等
我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他排序算法. 事实上, 桶排序较鸽巢排序更加的实用.
1 package offer; 2 3 4 public class BucketSort { 5 6 static void bucketsort(int data[],int min,int max) 7 { 8 int bucksize=max-min+1; 9 int bucket[]=new int[bucksize];10 int datalength=data.length;11 //打印数组12 System.out.println("排序之前:");13 for(int i=0;i<datalength;i++)14 System.out.print(data[i]+" ");15 System.out.println("\n");16 //确立每个元素的个数17 for(int i=0;i<datalength;i++)18 bucket[data[i]-min]++;19 //开始排序(实现一)20 // for(int i=0,j=0;i<bucksize;)21 // {22 // if(bucket[i]>0)23 // {24 // data[j]=i+min;25 // j++;26 // bucket[i]--;27 // }28 // else ++i;29 // }30 //实现二31 int j=0;32 for(int i=0;i<bucksize;i++)33 for(int k=0;k<bucket[i];++k)34 data[j++]=i+min;35 36 //打印数组37 System.out.println("排序之后:");38 for(int i=0;i<datalength;i++)39 System.out.print(data[i]+" ");40 41 }42 public static void main(String[] args)43 {44 int data[]={1,2,-2,3,4,1,3,-2,3,-3,-2,1,3,3,4};45 bucketsort(data,-3,4);46 }47 48 }
桶排序：
假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
此处介绍桶排序算法以及应用：http://hxraid.iteye.com/blog/647759
经典算法之排序问题（二）：桶排序、鸽巢排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。