資料結構
網路
關係資料庫管理系統
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go語言程式實現基數排序（降序排列整數）
基數排序是一種非比較排序演算法，它透過根據數字的有效位數將元素分配到不同的桶中來工作。在本文中，我們將探討一個 Go 語言程式，該程式實現基數排序以按降序排列整數。這裡我們將使用三種不同的方法：Getmax、countsort 和 radixsort，並結合示例來闡述這個概念。
語法
func getMax(arr []int) int
語法 "func getMax(arr []int) int" 定義了一個名為 "getMax" 的函式，它接受一個整數切片作為引數並返回一個整數值。
func countSort(arr []int, exp int)
語法 "func countSort(arr []int, exp int)" 定義了一個名為 "countSort" 的函式，它接受兩個引數：一個名為 "arr" 的整數切片和一個名為 "exp" 的整數。
func radixSort(arr []int)
語法 "func radixSort(arr []int)" 定義了一個名為 "radixSort" 的函式，它接受一個引數：一個名為 "arr" 的整數切片。
演算法
首先定義一個名為 RadixSort 的函式，該函式接受一個整數陣列作為輸入。
在輸入陣列中找到最大元素以確定最大數字中的位數。讓我們將此值稱為 max。
遍歷每個數字位置，從最低有效位到最高有效位。
在每次迭代中，建立 10 個桶（0 到 9）以根據當前位置的數字值臨時儲存整數。
遍歷輸入陣列中的每個整數，並根據當前位置的數字值將其分配到相應的桶中。
將所有整數分配到桶中後，按從 9 到 0 的桶順序將它們收集回輸入陣列。
對每個數字位置重複步驟 4-6，直到所有數字都處理完畢。
最後，輸入陣列將使用基數排序按降序排序。
示例
以下程式定義了三個函式：getMax、countSort 和 radixSort。getMax 函式在給定陣列中找到最大值。countSort 函式根據給定的指數 (exp) 執行計數排序。radixSort 函式透過重複呼叫 countSort 函式來實現基數排序，以處理每個數字位置。在主函式中，定義了一個整數陣列，然後應用基數排序以按降序排列陣列。排序前後的陣列都會被列印。
package main
import (
"fmt"
)
func getMax(arr []int) int {
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
return max
}
func countSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
count[(arr[i]/exp)%10]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
output[count[(arr[i]/exp)%10]-1] = arr[i]
count[(arr[i]/exp)%10]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSort(arr []int) {
max := getMax(arr)
for exp := 1; max/exp > 0; exp *= 10 {
countSort(arr, exp)
}
}
func main() {
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
fmt.Println("Array before sorting:", arr)
radixSort(arr)
fmt.Println("Array after sorting:", arr)
}
輸出
Array before sorting: [170 45 75 90 802 24 2 66] Array after sorting: [2 24 45 66 75 90 170 802]
結論
總之，我們探討了使用 Go 程式語言實現基數排序以按降序排列整數。基數排序是一種非比較排序演算法，它對要排序的數字的個位數字進行操作。在整篇文章中，我們演示了實現基數排序的分步方法，涵蓋了演算法中涉及的關鍵概念和操作。透過根據數字的有效位數將數字分配到不同的桶中，基數排序可以有效地對整數進行排序。
92 次瀏覽
