林河西网站建设,邢台网站优化公司,手机原理网站,网站排名5118桶排序
桶排序是一种分布排序#xff0c;将元素数组分到多个桶内#xff0c;然后每个桶再分别进行排序。
其计算复杂度取决于对桶内排序所用算法、使用桶数量以及输入均匀度。
主要流程如下
建立空桶数组将原始数组发布到各桶中对非空桶进行排序按照顺序从非空桶里面收集…桶排序
桶排序是一种分布排序将元素数组分到多个桶内然后每个桶再分别进行排序。
其计算复杂度取决于对桶内排序所用算法、使用桶数量以及输入均匀度。
主要流程如下
建立空桶数组将原始数组发布到各桶中对非空桶进行排序按照顺序从非空桶里面收集元素得到排序后的数组
func bucketSort(arr []int, numBuckets int) []int {if len(arr) 1 {return arr}// 根据数据最大最小值确定桶范围minVal, maxVal : findMinMax(arr)bucketRange : (maxVal - minVal 1) / numBuckets// 初始化桶buckets : make([][]int, numBuckets)for i : range buckets {buckets[i] make([]int, 0)}// 分布元素到桶中for _, num : range arr {bucketIndex : (num - minVal) / bucketRangeif bucketIndex numBuckets {bucketIndex-- // Adjusting for the last bucket}buckets[bucketIndex] append(buckets[bucketIndex], num)}// 桶内排序for _, bucket : range buckets {bucket insertionSort(bucket)}// 连接桶元素为排序数组sortedArr : make([]int, 0, len(arr))for _, bucket : range buckets {sortedArr append(sortedArr, bucket...)}return sortedArr
}func findMinMax(arr []int) (int, int) {minVal, maxVal : arr[0], arr[0]for _, num : range arr {if num minVal {minVal num}if num maxVal {maxVal num}}return minVal, maxVal
}func insertionSort(arr []int) []int {for i : 1; i len(arr); i {key : arr[i]j : i - 1for j 0 arr[j] key {arr[j1] arr[j]j--}arr[j1] key}return arr
}时间复杂度分析
最坏情况下如果数据分散聚集分布那么就很多集中在极少量的桶内这就会使得复杂度完全取决于桶内排序算法
在均匀分布情况 初始化桶并找到最大值 O(n) 分布到桶 O(n) 若桶内排序位插入排序 O ( n 2 k n ) O(\frac{n^2}{k}n) O(kn2n)其中k为桶数量 聚合成排序数组 O(k)
优化
一种常见的优化是先将桶中未排序的元素放回原始数组中然后对整个数组运行插入排序。因为插入排序的运行时间是基于每个元素与最终位置的距离所以比较的次数仍然相对较少并且通过将列表连续存储在内存中可以更好地利用内存层次结构
如果输入分布是已知的或可以估计的通常可以选择包含恒定密度的桶(而不仅仅是具有恒定大小)。这便能在即使分布非均匀情况下也能保证性能
基数排序
基数排序可以理解为一种特别的桶排序桶分布的规则是根据数字或者映射后数字的位数来决定的而桶内排序则是由所有位的位数排序来达成的
时间复杂度为O(nw)n为数据量w则为最长位数
将桶分为10个从最低位开始根据位的数字分配到相应桶这样从最低位到最高位排序完成之后就得到一个有序数组。 由于基数排序是根据之前排序完成之后的顺序去进行下一位的排序因此在下一位相同的情况下之前位的顺序依然是相对一致的。 代码实现如下
func radixSort(nums []int) []int {mx : getMax(nums)exp : 1// 从低位到高位进行排序for mx/exp 0 {nums countSort(nums, exp)exp * 10}return nums
}func countSort(nums []int, exp int) []int {n : len(nums)output : make([]int, n)count : make([]int, 10)// 统计当前位各个数字的个数for i : 0; i n; i {count[nums[i]/exp%10]}// 计算小于等于当前数字的总个数for i : 1; i 10; i {count[i] count[i-1]}// 根据之前小于等于的总个数获取到在当轮基数排序中的位置for i : n - 1; i 0; i-- {j : nums[i] / exp % 10output[count[j]-1] nums[i]count[j]--}// 更新排序后的数组for i : 0; i n; i {nums[i] output[i]}return nums
}func getMax(nums []int) int {mx : nums[0]for i : 1; i len(nums); i {if nums[i] mx {mx nums[i]}}return mx
}基数排序在元素范围较小时非常快但要求更多的空间以及缺少更多的灵活性 一种特别的应用场景是适合于顺序访问 MSD
MSD(Most Significant Digit)相比于上面的LSD(Least SIgnificant Digit)提出了新的思路。其从高位到低位进行递归排序
主要思路就是
根据当前位分到不同桶然后对于大于2的桶递归下一个低位进行排序最后将所有排序好的桶组合到返回值
相比于LSDMSD适合不定长的变量但不稳定(也可以稳定但实现更为复杂)性能更差些 另一个MSD独特的优势点就是MSD能够更好利用并发 func MSDRadixSort(nums []int, d int) {// 若已经到达最低位或者桶内元素低于两个直接返回if len(nums) 1 || d 0 {return}// 根据当前位放置到桶里buckets : make([][]int, 10)for i : 0; i len(buckets); i {buckets[i] make([]int, 0)}for _, num : range nums {digit : num / power(10, d-1) % 10buckets[digit] append(buckets[digit], num)}// 对每个桶往下位递归基数排序var i intfor _, bucket : range buckets {MSDRadixSort(bucket, d-1)copy(nums[i:], bucket)i len(bucket)}
}func power(base, exp int) int {ans : 1for i : 0; i exp; i {ans * base}return ans
}应用场景
适用于对空间不太敏感的场景且数据分布不是特别聚集对于大量数据难以一次在内存中排序的
Ref
https://en.wikipedia.org/wiki/Bucket_sorthttps://en.wikipedia.org/wiki/Radix_sort
