資料結構
網路
關係資料庫管理系統 (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
