排序算法 |
您所在的位置：网站首页 › 数据结构内排序是什么 › 排序算法 |
排序算法
|
桶排序(BucketSort)
概念介绍
桶排序主要适用于输入均匀分布在一个范围内的情况。 例如： 对范围从0.0到1.0并且均匀分布在整个范围内的大量浮点数，如何进行高效地排序? 使用基于比较的排序算法？基于比较排序算法的下界(合并排序，堆排序，快速排序…等)是Ω(nLogn)，也就是说，他们不能做得比nLogn更好。使用计算排序？计数排序在这里不能应用，因为在计数排序中使用键作为索引，但这里的键是浮点数。针对这种情况，可以使用桶排序。 桶排序（BucketSort) 是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数将待排序数组中的元素映射到各个对应的桶中，然后对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。 桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。 注意：桶排序的稳定性取决于桶内排序使用的算法。 排序思路将集合划分为多个范围相同的区间（桶），每个子区间自排序，最后合并。 bucketSort(arr[], n) 创建n个空桶(或列表)。对每个数组元素arr[i]执行以下操作。 通过映射函数 如 [n*数组[i]] 将待排序数组中的元素映射到各个对应的桶中 使用插入排序对单个桶进行排序。依次连接所有已排序的桶中数据集合。图示如下： 桶排序有相当的限制。因为桶的个数和大小都是人为设置的。而每个桶又要避免空桶的情况。 所以在使用桶排序的时候的要求如下： 待排序数列要求偏均匀，桶的设计（即映射函数）兼顾效率和空间，数据能在桶中均匀分配，如待排序数据有1000个，划分10个桶，则每个桶中的元素约100个最好。 时间复杂度桶排序的时间复杂度到底是多少？ 假设有n个待排序数字，分到m个桶中，如果分配均匀这样平均每个桶有n/m个元素。 桶排序的算法时间复杂度有两部分组成： 遍历处理每个元素，O(n)级别的普通遍历每个桶内再次排序的时间复杂度总和 如果桶内元素分配较为均匀，假设每个桶内部使用的排序算法为快速排序，那么每个桶内的时间复杂度为(n/m) log(n/m)。有m个桶，那么时间复杂度为m * (n/m)log(n/m)=n (log n-log m)最终桶排序的时间复杂度为：O(n)+O(n*(log n- log m))=O(n+n*(log n -log m)) 其中m为桶的个数如果到达极限情况n=m时。就能确保避免桶内排序，将数值放到桶中不需要再排序达到O(n)的排序效果,当然这种情况属于计数排序 源码示例 import java.util.Collections; import java.util.Vector; public class BucketSortExample { public static void main(String[] args) { //针对0-1范围内的浮点数排序 float arr[] = { 0.897F, 0.565F, 0.656F, 0.1234F, 0.665F, 0.3434F }; bucketSort2(arr); print(arr); //针对包含>1的浮点数排序 float arr1[] = {9.8F , 0.6F , 10.1F , 1.9F , 3.07F , 3.04F , 5.0F , 8.0F , 4.8F , 7.68F}; bucketSort2(arr1); print(arr1); } /** * 针对0-1范围内的浮点数排序 * @param arr */ static void bucketSort1(float arr[]) { int n = arr.length; if (n |
【本文地址】
今日新闻 |
推荐新闻 |