目录桶排序代码实现时间复杂度算法稳定性总结桶排序每个桶存储一定范围内的元素。通过函数一定的映射关系，将待排序数组中的元素映射到对应的各个桶中，对各个桶中的元素进行排序（也可以使用其他排序算法。或者继续递归使用桶排序），最后将非空桶中的元素一一放入原序列中。桶排序需要保证元素分布均匀，否则当所有数据都集中在同一个桶中时，桶排序就会失败。代码实现1.找到数组中的最大值max和最小值min，可以确定数组min~max的范围2.根据数据范围确定桶数1.如果桶数太多小，桶排序会失败2.如果桶太多，可能有些桶是空的。没有数据会造成空间浪费，所以桶的个数由我们自己决定，但是尽量让元素均匀分布在每个桶中。这里有一个方法（最大值-最小值）/每个桶可以放多少个不同的值+13.确定桶的区间，一般按照（最大值-最小值）/桶数，左闭右开publicclassBucketSort{publicstaticfinalint[]ARRAY={35,23,48,9,16,24,5,11,32,17};/***@parambucketSize是每个桶可以放多少个不同的值，也就是值的类型*比如当BucketSize==5时，桶可以存放{1,2,3,4,5}这些数字，*但是容量没有限制，就是可以存100个3*/publicstaticListsort(Listarray,intbucketSize){if(array==null||array.size()<2)返回数组；int最大值=数组。得到（0），最小值=数组。得到（0）；//找到最大最小值for(inti=0;imax)max=array.get(i);如果(array.get(i)>bucketArr=newArrayList<>(bucketCount);列表<整数>resultArr=newArrayList<>();for(inti=0;i());}//将原数组的数据分发到桶中for(inti=0;itemp=sort(bucketArr.get(i),bucketSize);对于(intj=0;jarray){for(inti:array){System.out.print(i+"");}System.out.println("");}publicstaticvoidmain(String[]args){print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()));系统输出。println("==============================================");print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()),2));}}时间复杂度桶排序算法遍历原数组两次，运算量为2N。最后，遍历桶输出排序结果的计算复杂度为N，初始化桶对桶排序的计算复杂度为M。不同的排序算法具有不同的算法复杂度。冒泡排序算法的复杂度是O(N^2)，堆排序和合并排序算法的复杂度是O(NlogN)。我们计算排序算法的复杂度为O(NlogN)，计算量为N/Mlog(N/M)M。最终计算量为3N+M+N/Mlog(N/M)M，即3N+M+N(logN-logM)，去掉系数，时间复杂度为O(N+M+N(logN-logM))稳定排序算法，相同元素排序后位置不会改变，所以桶排序算法是稳定排序算法。总结这篇文章就到这里了，希望可以帮到你
