永久网站域名,遵义市播州区住房和城乡建设局官方网站,企业网站模版,郑州网站建设找三牛排序
排序#xff1a;把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)
桶排序
根据元素的取值范围#xff0c;创建多个桶, 每个桶代表一个区间范围 创建桶的数量和范围需要尽可能保证元素能够被均匀分布 接下来将元素放进对应的桶中#xff0c;分别对每个桶中…排序
排序把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)
桶排序
根据元素的取值范围创建多个桶, 每个桶代表一个区间范围 创建桶的数量和范围需要尽可能保证元素能够被均匀分布 接下来将元素放进对应的桶中分别对每个桶中的元素进行排序 桶内采用的排序算法可自行决定均匀分布后每个桶内元素数量不会很多 最后按顺序将桶里的元素取出就完成了排序桶排序用的并不多主要体现在对于桶排序的应用: 计数排序和基数排序核心思想 基于最小值和最大值算出一个差值基于差值确定桶的数量和范围之后遍历数组中的每个元素来分配到不同的桶中对每一个桶进行单独的排序最后整合所有的桶即可
算法实现
1 定义桶数均匀分布
// 获取当前在第几个桶里
function getIndex(period, currentDist) {if (currentDist period) return 0;return Math.floor(currentDist / period);
}// 桶排序 主函数 list 待排序数组 n是定义的桶数量
function bucketSort(list, n 2) {// 计算最大值和最小值const max Math.max.apply(null, list);const min Math.min.apply(null, list);const dist max - min; // 最大值和最小值两者差距let buckets []; // 用于存放多个桶的总数组// n个桶, 每个桶内存放范围 dist / n 每个桶的间隔const period Math.ceil(dist / n);// 将列表中的数据分配到不同的桶里list.forEach((current) {const d current - min; // 当前与最小值的差距用于计算当前数据应该填充在哪个桶内const index getIndex(period, d); // 基于桶数和当前值算出应该存放到第几个桶内// 基于 index 来填充到对应的桶内!buckets[index] ? (buckets[index] [current]) : buckets[index].push(current);});// 对 buckets 中的每个桶进行排序buckets.map((bucket) {bucket.sort((a,b) a - b); // 这个使用默认的排序其实内部可以使用任意的排序算法return bucket;});// 对 buckets 中的每个桶进行合并 (拍平)buckets buckets.toString().split(,);return buckets.map(item item / 1);
}const list [102,103,108,107,101,102,102,102,107,103,109,108,102,101,104,102,104,106,109,102];
const result bucketSort(list, 5);
console.log(result); // [101, 101, 102, 102, 102, 102, 102, 102, 102, 103, 103, 104, 104, 106, 107, 107, 108, 108, 109, 109]总结
桶排序的时间复杂度 在 O(n) ~ O( n 2 n^2 n2)普通桶排序并不普遍应用是拆分为桶后在每个桶内还需要排序意义就不大了 而且要考虑每个桶内用什么样的数据结构来存储(考虑到内部排序) 如果还用数组就极大浪费了空间(需使用最大的空间, 不同语言有区别)一般可以使用链表但是对链表排序又开始麻烦了 桶排序优化空间时间上就会增加优化时间空间上又会增多, 取一个时间和空间的平衡 buckets.map 基本是常数级别这里实际上不怎么会消耗时间, 具体的sort算法可以使用任意的排序算法实现关于怎么处理和分配桶上述算法基于用户自行填入的桶数来均匀处理, 也可传入所有桶的范围分布列表那算法的细节实现就会不一样但基本思想是一致的虽然上述算法意义不大, 但是桶排序的意义在于其思想分而治之, 分配处理, 桶作为基本单位这个桶排序算法在开发中是比较重要的一种思想
