go语言实现基数排序高位优先

代码示例评论阅读5分52秒

要求:

1. 函数应接受一个整数数组作为输入,并返回排序后的结果。文章源自Golang编程指南-https://www.va26.com/work/316.html

2. 函数应使用基数排序算法进行排序,并确保高位优先。文章源自Golang编程指南-https://www.va26.com/work/316.html

3. 请在代码中添加必要的注释,以便他人理解。文章源自Golang编程指南-https://www.va26.com/work/316.html

4. 函数应具有良好的可读性和可维护性。文章源自Golang编程指南-https://www.va26.com/work/316.html

以下是一个使用基数排序算法实现的Go函数,按照高位优先的方式进行排序:文章源自Golang编程指南-https://www.va26.com/work/316.html

package main  
  
import (  
 "fmt"  
 "math"  
)  
  
// getMaxDigit 找到数组中的最大数的位数  
func getMaxDigit(arr []int) int {  
 maxDigit := 0  
 for _, num := range arr {  
 digit := int(math.Floor(math.Log10(float64(num))) + 1)  
 if digit > maxDigit {  
 maxDigit = digit  
 }  
 }  
 return maxDigit  
}  
  
// radixSort 高位优先的基数排序  
func radixSort(arr []int) []int {  
 // 1. 找到数组中最大数的位数  
 maxDigit := getMaxDigit(arr)  
  
 // 2. 创建一个桶数组  
 bucket := make([][]int, 10)  
 for i := range bucket {  
 bucket[i] = make([]int, 0)  
 }  
  
 // 3. 从最高位开始,对每个数进行排序  
 for d := maxDigit; d > 0; d-- {  
 // 每次循环开始时,需要将bucket清空  
 for i := range bucket {  
 bucket[i] = bucket[i][:0]  
 }  
  
 for _, num := range arr {  
 // 获取每个数的每一位  
 digit := (num / int(math.Pow(10, float64(d-1)))) % 10  
  
 // 将该数放入对应的桶中  
 bucket[digit] = append(bucket[digit], num)  
 }  
  
 // 4. 将各个桶中的数重新合并到arr中  
 index := 0  
 for _, b := range bucket {  
 for _, num := range b {  
 arr[index] = num  
 index++  
 }  
 }  
 }  
  
 return arr  
}  
  
func main() {  
 arr := []int{121, 432, 564, 23, 1, 45, 788}  
 sortedArr := radixSort(arr)  
 fmt.Println(sortedArr) // 输出: [1 23 45 121 432 564 788]  
}

注释已经嵌入在代码中,以帮助理解。文章源自Golang编程指南-https://www.va26.com/work/316.html

以下是这个基数排序代码实现的详细步骤解释:文章源自Golang编程指南-https://www.va26.com/work/316.html

定义getMaxDigit函数:文章源自Golang编程指南-https://www.va26.com/work/316.html

这个函数遍历整数数组,找出数组中最大数的位数。文章源自Golang编程指南-https://www.va26.com/work/316.html

它通过计算每个数字的位数(使用math.Log10函数和math.Floor函数),并记录遇到的最大位数。文章源自Golang编程指南-https://www.va26.com/work/316.html

定义radixSort函数:

这个函数是基数排序的主要实现。

首先,它调用getMaxDigit函数来确定数组中最大数的位数(maxDigit)。

初始化桶数组:

创建一个包含10个子数组的二维数组bucket,每个子数组代表一个桶,对应于一个数字(0-9)。

每个桶初始化为空数组,准备在接下来的排序过程中存放数字。

从最高位开始排序:

使用一个从maxDigit开始的递减循环,针对每一位进行排序。

在每次循环开始时,清空所有的桶,以便存放当前位的数字。

分配数字到桶中:

遍历整数数组,针对每个数字的当前位,计算其值(通过整数除法和模运算)。

将该数字放入对应当前位数字的桶中。

合并桶中的数字回到原数组:

遍历桶数组,按顺序将桶中的数字放回原数组。

这样,原数组就根据当前位的数字进行了排序。

继续下一位的排序:

重复步骤4-6,直到处理完数字的最低位。

返回排序后的数组:

经过上述步骤,整数数组已经按照高位优先的顺序排好了序。

函数返回排序后的数组。

主函数main中的示例:

定义了一个示例数组arr。

调用radixSort函数对数组进行排序。

打印排序后的数组,验证排序结果。

整个基数排序过程中,最关键的思想是按照数字的每一位来进行排序,从高位到低位依次进行。通过这种方式,即使是大整数也能被有效地排序,而且基数排序是一种稳定的排序算法,相同值的元素在排序后会保持原有的顺序。

这个基数排序函数首先找到输入数组中的最大数的位数,然后从最高位开始,根据每一位的数字将数组中的数分配到10个桶中。最后,将各个桶中的数重新合并到原始数组中。这个过程会重复进行,直到处理完最低位。

 
  • 本文由golang编程指南作者原创,请勿恶意转载!
  • 转载请务必保留本文链接:https://www.va26.com/work/316.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证