数据结构
网络
关系数据库管理系统 (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+ 浏览量
