桶排序(Bucket sort )或所谓的盒排序是一种排序算法,原理是将数组分成有限数量的桶。 对每个时段分别进行排序。 您可以使用其他排序算法,也可以使用递归时段排序继续排序。 桶排序是鸽巢排序的总结结果。 如果要排序的数组中的数值是均匀分配的,则桶排序使用线性时间((n ) )。 但是,桶排序不是比较排序,不受o(nlogn )下限的影响。 定义
假设:输入是均匀分布在由随机进程生成的[ 0,1 ]区间的实数。 将区间[ 0,1 ]分为大小相等的n个子区间(桶),桶1/n )、1/n、(1/n,2/n,3/n )、…、(k/n,(k 1 ) ) 算法设定定量数组作为空桶。
找个顺序,把项目一个个放进对应的桶里去。
按非空桶排序。 您可以继续使用其他排序算法,如桶排序和插入排序
从非空桶中将项目恢复为原始序列。
其伪代码是Java实现源代码分析
首先,创建一个对指定数组进行排序的方法。 该方法包括两个步骤:获取与要排序的列的最大值相对应的要除法的值-divisionValueOfSequence。 这个参数的作用是告诉我们现在我们需要排序的是数列中的一位数字(个/十/百/千位……)
调用子方法进行排序。 排序按要排序的数字中指定位数的数字进行排序
其中,getDivisionValueOfSequence方法实现如下:
然后按指定的位数排序。 排序对象的位数可以从divisionValueOfSequence求出。 执行键为value/divisionValue表达式biaoshi获取指定位数的值(0-9),并将其作为桶的序号
放入对应的桶后,需要对桶中的集合进行排序(反复调用)。
最后用水桶排序的值必须放入原始值
可以看到,桶排序是参考数组的索引也实际排序的规律进行排序的。 在此逻辑中,只要根据指定的规则将数据放在相应的排序位置,就会对结果进行排序
另外,在这个安装中,为了简单起见,经常制作bucketArray,但是在实用上bucketArray还有优化的余地。 场景限制和应用
桶排序的复杂度信息如下。
桶排序的复杂性
时段排序限制:数据的长度通常必须相同,或可以转换为相同类型
因为是按映射排序的,所以必须定义中间变量并保存中间值
其应用场景:排序对象数据集中
数据量大,其他比较排序算法中比较次数过多
源代码如下所示。
package com.hbhs.algorithm.sort;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
/*** Bucket sort
*桶排序(Bucket sort )或所谓的盒排序是一种排序算法,原理是将数组分成有限数量的桶。 对每个桶分别排序。 您可以使用其他排序算法,也可以继续使用桶排序递归排序。 桶排序是鸽巢排序的总结结果。 如果要排序的数组中的数值是均匀分配的,则桶排序使用线性时间((n ) )。 但是,桶排序不是比较排序,不受o(nlogn )下限的影响。
*
执行流程如下
* 1作为空桶设定定量排列。
* 2寻找麦片,将各项逐一放入对应的桶中。
* 3按非空桶排序。
* 4从非空桶中将项目恢复到原始序列。
* @author walter.xu**/
public class BucketSort {
/***桶排序* @param sequenceList*/
publicstaticvoidsort (listsequencelist ) (
求出应该除以//1sequence的值,返回值为10/100/1000/10000 . intdivisionvalueofsequence=getdivisionvalueofsequence (sequence luence
用//2除数计算sort (sequence list,divisionValueOfSequence );
}
//privatestaticvoidsort (按指定的位数排序listsequencelist,int divisionValue ) )。
//1初始化要比较的桶数组。 类型为List,要保存的是序列List[] bucketArray=new List[10];
//2重复待排序序列,在对应的桶中放入for(intvalue:sequencelist )
int index=value/divisionValue; //获取此运算需要排序的位数,在对应的桶中输入bucket array (index )==null (bucket array ) index )=newarraylist );
bucketArray[index].add(value;
}
//4重复桶排队,对每个桶的数据进行排序。 这里也是桶排序(也可以采用诸如插入排序之类的其它排序方法) (if ) (divisionvalue1) )。
列表备份数据列表:备份阵列(for ) {
备份数据列表!=nullbucketdatalist.size(0) sort (bucket datalist,divisionValue/10 );
}
//明确数据并根据bucket的重置进行排序的序列sequenceList.clear (;
列表列表:备份阵列(for ) {
if (列表!=nulllist.size(0) sequencelist.addall ) list;
}
}
privatestaticintgetdivisionvalueofsequence (listsequencearray ) {
//计算要排序的最大值intmax=sequencearray.get(0)
输入目标3360序列阵列(for ) {
目标最大(if )最大=目标;
}
//求出第一次除数时,只能为10^nint divisionValue=1;
wile(max=10 ) {
divisionValue *=10;
max /=10;
}
return divisionValue;
}
}