做网站宣传,百度权重查询网站,个人如何做网站软件,领星erp系统基本思想 将整数按位数切割成不同的数字#xff0c;然后从低位开始#xff0c;依次到高位#xff0c;逐位进行排序#xff0c;从而达到排序的目的。
算法步骤 基数排序算法可以采用「最低位优先法#xff08;Least Significant Digit First#xff09;」或者「最高位优先…基本思想 将整数按位数切割成不同的数字然后从低位开始依次到高位逐位进行排序从而达到排序的目的。
算法步骤 基数排序算法可以采用「最低位优先法Least Significant Digit First」或者「最高位优先法Most Significant Digit first」。最常用的是「最低位优先法」。 下面我们以最低位优先法为例讲解一下算法步骤。
确定排序的最大位数遍历数组元素获取数组最大值元素并取得对应位数。从最低位个位开始到最高位为止逐位对每一位进行排序 定义一个长度为 10的桶数组 buckets每个桶分别代表 0∼9 中的 1 个数字。按照每个元素当前位上的数字将元素放入对应数字的桶中。清空原始数组然后按照桶的顺序依次取出对应元素重新加入到原始数组中。
以 [692,924,969,503,871,704,542,436]为例演示一下基数排序算法的整个步骤。 适用场景 大规模整数排序固定长度数据排序稳定性要求高的排序场景数据分布较为均匀的情况外部排序场景
排序稳定性 基数排序采用的桶排序是稳定的。基数排序是一种 稳定排序算法。
代码实现(golang)
func getMax(arr []int) int {max : arr[0]for _, v : range arr {if v max {max v}}return max
}func radixSort(arr []int) []int {max : getMax(arr)exp : 1for max/exp 0 {buckets : make([][]int, 10)for _, v : range arr {digit : (v / exp) % 10buckets[digit] append(buckets[digit], v)}arr []int{}for _, bucket : range buckets {arr append(arr, bucket...)}exp * 10}return arr
}func main() {arr : []int{170, 45, 75, 90, 802, 24, 2, 66}sortedArr : radixSort(arr)fmt.Println(sortedArr)
}
