資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Go語言實現歸併排序
在這篇 Go 語言文章中，我們將學習如何使用三種不同的方法（遞迴、迭代和 goroutine）在 Go 語言中實現歸併排序。歸併排序是最有效的排序演算法之一，它使用分治法來排序元素列表。
語法
func copy(dst, str[] type) int
Go 語言中的 copy 函式用於將一個源陣列的值複製到目標陣列，並返回已複製元素的數量作為結果。它接收兩個陣列作為引數。
func len(v Type) int
len() 函式用於獲取任何引數的長度。它接收一個數據型別變數作為引數，我們希望找到該變數的長度，並返回一個整數作為變數的長度。
演算法
步驟 1 − 首先，我們需要匯入 fmt 包。
步驟 2 − 現在，定義一個名為 mergeSort 的函式，該函式接收一個整數陣列作為引數，並返回排序後的陣列。
步驟 3 − 在函式內部，如果陣列的長度小於或等於 1，則返回整個陣列，因為無法對陣列中的單個元素進行排序。然後找到給定陣列的中點。
步驟 4 − 遞迴呼叫 mergeSort() 函式處理陣列的左半部分，並將結果儲存到名為 left 的變數中。
步驟 5 − 同樣，再次遞迴呼叫 mergeSort() 函式處理陣列的右半部分，並將結果儲存到名為 right 的變數中。
步驟 6 − 使用左陣列和右陣列作為輸入呼叫 merge 函式，並返回結果。
步驟 7 − merge() 函式接收左陣列和右陣列作為引數，並使用 for 迴圈和 if 條件將它們組合到單個數組中。
步驟 8 − 現在，啟動 main() 函式。在 main() 函式內部，初始化要排序的陣列，並在螢幕上列印它們。
步驟 9 − 此外，透過將初始化的陣列作為引數傳遞給函式來呼叫 mergeSort() 函式。將函式獲得的結果儲存在一個變數中，並在螢幕上列印它們。
示例 1
遞迴是實現歸併排序最常見的方法。在這種方法中，我們將給定資料分成兩半，然後遞迴地對每一半進行排序。然後透過合併排序後的兩半，我們完全實現了歸併排序。
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
middle := len(arr) / 2
left := mergeSort(arr[:middle])
right := mergeSort(arr[middle:])
return merge(left, right)
}
func merge(left, right []int) []int {
result := make([]int, len(left)+len(right))
i, j := 0, 0
for k := 0; k < len(result); k++ {
if i >= len(left) {
result[k] = right[j]
j++
} else if j >= len(right) {
result[k] = left[i]
i++
} else if left[i] < right[j] {
result[k] = left[i]
i++
} else {
result[k] = right[j]
j++
}
}
return result
}
func main() {
arr := []int{5, 2, 6, 3, 1, 4}
fmt.Println("The given unsorted array is:", arr)
sorted := mergeSort(arr)
fmt.Println("The sorted array is:", sorted)
}
輸出
The given unsorted array is: [5 2 6 3 1 4] The sorted array is: [1 2 3 4 5 6]
示例 2
在這個示例中，我們將使用迭代變數來實現陣列的歸併排序。在這種方法中，我們將使用各種內建函式，如 copy() 和 len()，以及 for 迴圈和 if 條件來實現結果。
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
size := 1
for size < len(arr) {
for left := 0; left < len(arr)-1; left += size * 2 {
middle := left + size - 1
right := min(left+size*2-1, len(arr)-1)
merged := merge(arr[left:middle+1], arr[middle+1:right+1])
copy(arr[left:right+1], merged)
}
size *= 2
}
return arr
}
func merge(left, right []int) []int {
result := make([]int, len(left)+len(right))
i, j := 0, 0
for k := 0; k < len(result); k++ {
if i >= len(left) {
result[k] = right[j]
j++
} else if j >= len(right) {
result[k] = left[i]
i++
} else if left[i] < right[j] {
result[k] = left[i]
i++
} else {
result[k] = right[j]
j++
}
}
return result
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
arr := []int{5, 2, 6, 3, 1, 4}
fmt.Println("The given unsorted array is:", arr)
sorted := mergeSort(arr)
fmt.Println("The obtained sorted array is:", sorted)
}
輸出
The given unsorted array is: [5 2 6 3 1 4] The obtained sorted array is: [1 2 3 4 5 6]
示例 3
在這個示例中，我們將使用 goroutine 來實現歸併排序。Goroutine 可以定義為允許我們使用併發程式設計的輕量級執行緒。
package main
import "fmt"
func mergeSort(arr []int, c chan []int) {
if len(arr) <= 1 {
c <- arr
return
}
middle := len(arr) / 2
leftChan := make(chan []int)
rightChan := make(chan []int)
go mergeSort(arr[:middle], leftChan)
go mergeSort(arr[middle:], rightChan)
left := <-leftChan
right := <-rightChan
c <- merge(left, right)
}
func merge(left, right []int) []int {
result := make([]int, len(left)+len(right))
i, j := 0, 0
for k := 0; k < len(result); k++ {
if i >= len(left) {
result[k] = right[j]
j++
} else if j >= len(right) {
result[k] = left[i]
i++
} else if left[i] < right[j] {
result[k] = left[i]
i++
} else {
result[k] = right[j]
j++
}
}
return result
}
func main() {
arr := []int{15, 21, 6, 30, 16, 43}
fmt.Println("Unsorted array:", arr)
c := make(chan []int)
go mergeSort(arr, c)
sorted := <-c
fmt.Println("Sorted array:", sorted)
}
輸出
Unsorted array: [15 21 6 30 16 43] Sorted array: [6 15 16 21 30 43]
結論
我們已經成功編譯並執行了一個 Go 語言程式來實現歸併排序以及示例。在這篇文章中，我們使用了三個程式。在第一個程式中，我們使用遞迴的概念來實現結果，而在第二個和第三個程式中，我們分別使用內部庫函式和 goroutine。
1K+ 瀏覽量
