資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
