数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用Go语言实现基数排序
在这篇文章中，我们将了解如何使用最低有效位和最高有效位来实现基数排序。基数排序是一种排序算法，它通过根据元素的个位数字或数字位置对元素进行分组来进行排序。它是一种线性时间排序算法，时间复杂度为O(nk)。
使用最低有效位
在这种方法中，我们将编写一个Go语言程序，使用最低有效位来实现基数排序。LSD 从右到左对元素进行排序，比较它们的个位数字。
算法
步骤 1 − 首先，我们需要导入fmt包。然后创建一个名为radixSortMSD()的函数来对数组进行排序。
步骤 2 − 在函数内部创建一个新数组。使用for循环迭代数组，并将数组的最大元素存储在一个变量中。
步骤 3 − 现在，初始化一个计数数组来跟踪具有特定数字的元素数量。
步骤 4 − 遍历数组并为每个元素的对应数字递增计数。
步骤 5 − 修改计数数组以存储每个元素在输出数组中的实际位置。按照计数数组指定的顺序将元素从输入数组复制到输出数组。
步骤 6 − 将输入数组更新为排序后的输出数组并返回排序后的数组。
步骤 7 − 启动main()函数。在main()内部初始化一个数组并向其存储值。此外，调用radixSort()函数并将数组作为参数传递给函数。
步骤 8 − 将函数获得的结果存储在一个变量中，并在屏幕上打印。
示例
下面的示例演示了如何开发一个Go语言程序，使用最低有效位来实现基数排序。
package main
import "fmt"
func radixSortLSD(arr []int) []int {
max := arr[0]
for i := 1; i < len(arr); i++ {
if arr[i] > max {
max = arr[i]
}
}
exp := 1
for max/exp > 0 {
count := make([]int, 10)
for i := 0; i < len(arr); i++ {
count[(arr[i]/exp)%10]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
Output := make([]int, len(arr))
for i := len(arr) - 1; i >= 0; i-- {
Output[count[(arr[i]/exp)%10]-1] = arr[i]
count[(arr[i]/exp)%10]--
}
for i := 0; i < len(arr); i++ {
arr[i] = Output[i]
}
exp *= 10
}
return arr
}
func main() {
arr := []int{15, 31, 42, 20, 9}
fmt.Println("The unsorted array is:", arr)
result := radixSortLSD(arr)
fmt.Println("The sorted array is:", result)
}
输出
The unsorted array is: [15 31 42 20 9] The sorted array is: [9 15 20 31 42]
使用最高有效位
在这种方法中，我们将编写一个Go语言程序，使用以下语法通过最高有效位使用基数排序来对数组进行排序。
语法
func len(v Type) int
len()函数用于获取任何参数的长度。它接受一个参数作为我们希望查找其长度的数据类型变量，并返回一个整数作为变量的长度。
算法
步骤 1 − 首先，我们需要导入fmt包。然后我们创建了两个名为radixSortMSD()和radixSortMSDHelper()的函数。
步骤 2 − radixSort()函数接受要排序的数组作为参数，并返回排序后的数组。该函数调用radixSortMSDHelper()函数。
步骤 3 − radixSortMSDHelper()函数接受要排序的数组以及数组的最大元素作为参数。
步骤 4 − 该函数将排序后的数组返回给radixSort()函数，radixSort()函数最终将数组返回给程序的main()部分。
步骤 5 − 现在，启动main()函数。在main()内部初始化要排序的数组并为其赋值。
步骤 6 − 通过将数组作为参数传递给函数来进一步调用radixSortMSD()函数，并将结果存储在一个单独的变量中。
步骤 7 − 现在，使用fmt.Println()函数在屏幕上打印最终数组。
示例
在下面的示例中，我们将学习如何开发一个Go语言程序，使用最高有效位来实现基数排序。
package main
import "fmt"
func radixSortMSD(arr []int) []int {
max := arr[0]
for i := 1; i < len(arr); i++ {
if arr[i] > max {
max = arr[i]
}
}
arr = radixSortMSDHelper(arr, max)
return arr
}
func radixSortMSDHelper(arr []int, exp int) []int {
if exp <= 0 {
return arr
}
count := make([]int, 10)
for i := 0; i < len(arr); i++ {
count[(arr[i]/exp)%10]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
Output := make([]int, len(arr))
for i := len(arr) - 1; i >= 0; i-- {
Output[count[(arr[i]/exp)%10]-1] = arr[i]
count[(arr[i]/exp)%10]--
}
subarrays := make([][]int, 10)
for i := 0; i < len(Output); i++ {
subarrays[(Output[i]/exp)%10] = append(subarrays[(Output[i]/exp)%10], Output[i])
}
result := make([]int, 0)
for i := 0; i < 10; i++ {
if len(subarrays[i]) > 0 {
subarrays[i] = radixSortMSDHelper(subarrays[i], exp/10)
result = append(result, subarrays[i]...)
}
}
return result
}
func main() {
arr := []int{5, 3, 2, 15, 9}
fmt.Println("The unsorted array is:", arr)
result := radixSortMSD(arr)
fmt.Println("The sorted array is:", result)
}
输出
The unsorted array is: [5 3 2 15 9] The sorted array is: [2 3 5 9 15]
结论
我们已经成功编译并执行了一个Go语言程序，使用基数排序算法对数组进行排序。这里我们实现了两个示例。在第一个示例中，我们通过最低有效位对数组进行排序，而在第二个示例中，我们通过最高有效位对数组进行排序。两种方法的时间复杂度均为O(nk)。
浏览量：362
