資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用桶排序作為子程式的 Go 語言基數排序實現
子程式是程式的一部分，它執行特定任務，並且可以根據目的和用途重複呼叫。當呼叫子程式時，程式會跳轉到該例程並執行該例程內的指令。基數排序是一種根據數字對元素進行排序的演算法。它具有線性時間複雜度，用於排序大量資料。它使用計數排序來計算數字的頻率。在這篇 Go 語言文章中，我們將編寫程式來實現使用桶排序作為子程式的基數排序。
語法
func len(v Type) int
要確定任何引數的長度，請使用 len() 函式。它接受一個輸入，並返回一個整數，表示變數的長度。
func make ([] type, size, capacity)
Go 中的 make 函式用於構建陣列/對映。它接收要生成的變數型別及其大小和容量作為引數。
func range(variable)
range 函式迭代任何資料型別。要使用它，我們必須首先放置 range 關鍵字，然後是我們要迭代到的資料型別，迴圈將迭代到變數的最後一個元素。
演算法
步驟 1 - 建立一個 bucketSort 函式。
步驟 2 - 查詢陣列的最大元素。
步驟 3 - 對於每個數字位置，執行基數排序
步驟 4 - 使用 LSD 方法實現基數排序
步驟 5 - 使用迭代方法實現基數排序
示例 1：最低有效位 (LSD)
在這個例子中，我們將編寫一個 Go 語言程式來實現使用桶排序作為子程式的基數排序。在此方法中，元素根據數字分佈到桶中，並在每個數字位置按原始順序重建。
package main
import (
"fmt"
"math"
)
func main() {
array := []int{10, 14, 2, 43, 65, 76, 23, 674}
fmt.Println("Before sorting :", array)
radixSortLSD(array)
fmt.Println("After sorting :", array)
}
func bucketSort(arr []int, exp int) {
n := len(arr)
buckets := make([][]int, 10)
for i := 0; i < 10; i++ {
buckets[i] = make([]int, 0)
}
for i := 0; i < n; i++ {
digit := (arr[i] / exp) % 10
buckets[digit] = append(buckets[digit], arr[i])
}
index := 0
for i := 0; i < 10; i++ {
for j := 0; j < len(buckets[i]); j++ {
arr[index] = buckets[i][j]
index++
}
}
}
func radixSortLSD(arr []int) {
max := int(math.Inf(-1))
for _, num := range arr {
if num > max {
max = num
}
}
exp := 1
for exp <= max {
bucketSort(arr, exp)
exp *= 10
}
}
輸出
Before sorting : [10 14 2 43 65 76 23 674] After sorting : [2 10 14 23 43 65 76 674]
示例 2：使用迭代
在這個例子中，我們將編寫一個 Go 語言程式來實現使用桶排序作為子程式的基數排序。在此方法中，元素根據其數字迭代地分佈到桶中。
package main
import (
"fmt"
"math"
)
func bucketSort(arr []int, exp int) {
n := len(arr)
buckets := make([][]int, 10)
for i := 0; i < 10; i++ {
buckets[i] = make([]int, 0)
}
for i := 0; i < n; i++ {
digit := (arr[i] / exp) % 10
buckets[digit] = append(buckets[digit], arr[i])
}
index := 0
for i := 0; i < 10; i++ {
for j := 0; j < len(buckets[i]); j++ {
arr[index] = buckets[i][j]
index++
}
}
}
func radixSortIterative(arr []int) {
max := int(math.Inf(-1))
for _, num := range arr {
if num > max {
max = num
}
}
for exp := 1; max/exp > 0; exp *= 10 {
bucketSort(arr, exp)
}
}
func main() {
array := []int{11, 15, 1, 42, 64, 78, 23, 674}
fmt.Println("Before Sorting:", array)
radixSortIterative(array)
fmt.Println("After sorting :", array)
}
輸出
Before Sorting: [11 15 1 42 64 78 23 674] After sorting : [1 11 15 23 42 64 78 674]
結論
在本文中，我們檢查瞭如何在 Go 語言中使用桶排序作為子程式執行基數排序。我們探索了使用迭代和 LSD 方法實現此程式。
更新於：2023年7月6日
93 次瀏覽
廣告