数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用计数排序作为子程序的 Go 语言基数排序程序
基数排序是一种根据数字对元素进行排序的算法。它具有线性时间复杂度，用于对大量数据进行排序。它使用计数排序来计算数字的频率。
计数排序是一种有效的排序算法，当输入是在特定范围内的整数时。它计算输入中每个唯一元素出现的次数，并使用这些信息来获取每个元素的正确位置。
子程序是程序的一个函数，它执行特定的任务，并且可以在程序中需要时重复调用。
语法
func len(v Type) int
len() 方法返回任何参数的长度。它接受一个输入，即我们要了解其长度的数据类型变量，并返回一个整数，即变量的长度。
func make ([] type, size, capacity)
Go 中的 make 函数用于构建数组/映射。它接收要生成的变量的类型以及其大小和容量作为参数。
func range(variable)
range 函数迭代任何数据类型。要使用它，我们必须首先放置 range 关键字，然后是我们要迭代的数据类型，循环将迭代直到变量的最后一个元素。
算法
步骤 1 − 此程序导入 fmt、main 和 math 作为必要的包
步骤 2 − 创建一个名为 find_max 的函数来查找数组中的最大元素
步骤 3 − 对于每一位，使用计数排序算法，从最低有效位到最高有效位
步骤 4 − 现在创建一个大小为 10 的整数计数数组，并将计数数组设置为全零。
步骤 5 − 更新计数数组以存储每一位的累积计数。这显示了每一位在输出数组中的起始位置
步骤 6 − 然后，以相反的顺序遍历输入数组，并根据当前数字将每个元素放置在输出数组中的正确位置
步骤 7 − 将输出数组放回输入数组，每次迭代将 exp 增加 10 倍，在所有迭代之后，输入数组将按非递减顺序排序
示例 1：使用重复
在本例中，我们将编写一个 Go 语言程序，使用计数排序作为子程序来实现基数排序，其中计数排序计算每一位，基数排序重复调用计数排序来对数组进行排序。
package main
import (
"fmt"
"math"
)
func findmaximum(array []int) int {
maximum := math.MinInt64
for _, number := range array {
if number > maximum {
maximum = number
}
}
return maximum
}
func countsort(array []int, exp int) {
m := len(array)
output := make([]int, m)
count := make([]int, 10)
for a := 0; a < 10; a++ {
count[a] = 0
}
for a := 0; a < m; a++ {
index := (array[a] / exp) % 10
count[index]++
}
for a := 1; a < 10; a++ {
count[a] += count[a-1]
}
for a := m - 1; a >= 0; a-- {
index := (array[a] / exp) % 10
output[count[index]-1] = array[a]
count[index]--
}
for a := 0; a < m; a++ {
array[a] = output[a]
}
}
func radsorting(array []int) {
maximum := findmaximum(array)
for exp := 1; maximum/exp > 0; exp *= 10 {
countsort(array, exp)
}
}
func main() {
array := []int{10, 12, 18, 02, 04, 95, 72, 62}
fmt.Println("The Unsorted array is:", array)
radsorting(array)
fmt.Println("After sorting:", array)
}
输出
Original aray is : [10 12 18 2 4 95 72 62] The Sorted array: [2 4 10 12 18 62 72 95]
示例 2：使用队列的迭代实现
在本例中，我们将编写一个 Go 语言程序，使用计数排序作为子程序来实现基数排序，其中涉及从 LSD 到 MSD 处理每一位。
package main
import (
"fmt"
)
type Queue struct {
elements []int
}
func (q *Queue) Enqueue(element int) {
q.elements = append(q.elements, element)
}
func (q *Queue) Dequeue() int {
element := q.elements[0]
q.elements = q.elements[1:]
return element
}
func (q *Queue) IsEmpty() bool {
return len(q.elements) == 0
}
func getmaximum(arr []int) int {
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
return max
}
func radixSorting(arr []int) []int {
max := getmaximum(arr)
digits := 0
for max > 0 {
max /= 10
digits++
}
for i := 0; i < digits; i++ {
queues := make([]*Queue, 10)
for j := 0; j < 10; j++ {
queues[j] = &Queue{elements: []int{}}
}
for _, num := range arr {
digit := (num / Pow(10, i)) % 10
queues[digit].Enqueue(num)
}
index := 0
for j := 0; j < 10; j++ {
for !queues[j].IsEmpty() {
arr[index] = queues[j].Dequeue()
index++
}
}
}
return arr
}
func Pow(base, exp int) int {
result := 1
for exp > 0 {
if exp&1 != 0 {
result *= base
}
base *= base
exp >>= 1
}
return result
}
func main() {
arr := []int{110, 223, 45, 50, 812, 84, 21, 17}
sorted := radixSorting(arr)
fmt.Println("Array after sorting:", sorted)
}
输出
Array after sorting : [17 21 45 50 84 110 223 812]
示例 3：原地基数排序
在本例中，我们将编写一个 Go 语言程序，使用计数排序作为子程序来实现基数排序。在这种方法中，排序是在原地进行的，这意味着它不需要与输入成比例的额外空间。
package main
import (
"fmt"
)
func getMax(array []int) int {
max := array[0]
for _, num := range array {
if num > max {
max = num
}
}
return max
}
func countingSort(array []int, exp int) {
n := len(array)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
index := (array[i] / exp) % 10
count[index]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
index := (array[i] / exp) % 10
output[count[index]-1] = array[i]
count[index]--
}
for i := 0; i < n; i++ {
array[i] = output[i]
}
}
func radixSort(arr []int) {
max := getMax(arr)
exp := 1
for exp <= max {
countingSort(arr, exp)
exp *= 10
}
}
func main() {
array := []int{15, 65, 32, 34, 435, 87, 56, 86}
radixSort(array)
fmt.Println("Array after sorting :", array)
}
输出
Array after sorting: [15 32 34 56 65 86 87 435]
结论
在本文中，我们检查了如何使用不同的 Go 语言方法对未排序的数组执行基数排序，然后打印排序后的数组。我们探索了使用重复、迭代以及原地基数排序来实现此程序。
136 次浏览
