Go 归并排序教程
最后修改于 2025年3月8日
本教程将探讨 Go 中的归并排序算法，演示其如何用于升序和降序排序数值和文本数据，并与快速排序进行基准测试。
一个 算法 是一个结构化的步骤序列，用于高效地解决问题或执行任务。它是编程的基石，驱动着计算解决方案。
排序 是指将数据组织成特定的序列，例如升序或降序。它对于在各种应用程序中增强数据检索和分析至关重要。
常用排序算法
以下是一些著名的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
归并排序算法
归并排序是一种分治算法，它将数组分成两个部分，递归地对每个部分进行排序，然后将它们按排序顺序合并在一起。
归并排序具有稳定的 O(n log n) 时间复杂度，效率高，但需要额外的空间进行合并。它非常适合链表和大型数据集。
归并排序示例
下面是 Go 中用于数字和字符串的归并排序实现。
merge_sort.go
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergeSort(arr[:mid])
right := mergeSort(arr[mid:])
return merge(left, right)
}
func merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] < right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
func mergeSortStrings(arr []string) []string {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergeSortStrings(arr[:mid])
right := mergeSortStrings(arr[mid:])
return mergeStrings(left, right)
}
func mergeStrings(left, right []string) []string {
result := make([]string, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] < right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
func sortDescending(arr []int) []int {
sorted := mergeSort(arr)
for i, j := 0, len(sorted)-1; i < j; i, j = i+1, j-1 {
sorted[i], sorted[j] = sorted[j], sorted[i]
}
return sorted
}
func sortStringsDescending(arr []string) []string {
sorted := mergeSortStrings(arr)
for i, j := 0, len(sorted)-1; i < j; i, j = i+1, j-1 {
sorted[i], sorted[j] = sorted[j], sorted[i]
}
return sorted
}
func main() {
numbers := []int{38, 27, 43, 3, 9, 82, 10}
words := []string{"apple", "banana", "cherry", "date", "elderberry"}
fmt.Println("Sorted numbers (ascending):", mergeSort(numbers))
fmt.Println("Sorted numbers (descending):", sortDescending(numbers))
fmt.Println("Sorted words (ascending):", mergeSortStrings(words))
fmt.Println("Sorted words (descending):", sortStringsDescending(words))
}
mergeSort 函数递归地分割和合并整数切片，而 mergeSortStrings 则对字符串执行相同的操作。merge 辅助函数将已排序的两个部分合并。
对于降序，sortDescending 和 sortStringsDescending 会反转升序结果。这种方法利用了 Go 的切片操作的清晰性和效率。
$ go run merge_sort.go Sorted numbers (ascending): [3 9 10 27 38 43 82] Sorted numbers (descending): [82 43 38 27 10 9 3] Sorted words (ascending): [apple banana cherry date elderberry] Sorted words (descending): [elderberry date cherry banana apple]
归并排序与快速排序的比较
归并排序保证 O(n log n) 的时间复杂度和稳定性，使其可靠。快速排序的平均时间复杂度为 O(n log n)，但在最坏情况下（例如已排序的数据）可能退化到 O(n²)。
此基准测试比较了它们在 Go 中处理大型数据集时的性能。
benchmark.go
package main
import (
"fmt"
"math/rand"
"time"
)
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergeSort(arr[:mid])
right := mergeSort(arr[mid:])
return merge(left, right)
}
func merge(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] < right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
func quickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left := []int{}
middle := []int{}
right := []int{}
for _, x := range arr {
if x < pivot {
left = append(left, x)
} else if x == pivot {
middle = append(middle, x)
} else {
right = append(right, x)
}
}
left = quickSort(left)
right = quickSort(right)
return append(append(left, middle...), right...)
}
func main() {
rand.Seed(time.Now().UnixNano())
numbers := make([]int, 10000)
for i := range numbers {
numbers[i] = rand.Intn(10000)
}
mergeData := make([]int, len(numbers))
copy(mergeData, numbers)
start := time.Now()
mergeSort(mergeData)
mergeTime := time.Since(start)
quickData := make([]int, len(numbers))
copy(quickData, numbers)
start = time.Now()
quickSort(quickData)
quickTime := time.Since(start)
fmt.Printf("Merge Sort Time: %.6f seconds\n", mergeTime.Seconds())
fmt.Printf("Quick Sort Time: %.6f seconds\n", quickTime.Seconds())
}
此基准测试在 10,000 个随机整数上测试归并排序和快速排序。归并排序在合并过程中创建新的切片，而快速排序以类似的递归方式进行分区。
归并排序可预测的性能与快速排序由于更好的缓存局部性而具有的潜在速度优势形成对比。实际结果各不相同，但归并排序可确保一致性。
来源
本教程解释了 Go 中的归并排序，提供了数字和文本的示例，并与快速排序进行了基准测试。