package main
import (
"fmt"
)
// merge 合并两个有序数组
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++
}
}
// 追加剩余的元素
for i < len(left) {
result = append(result, left[i])
i++
}
for j < len(right) {
result = append(result, right[j])
j++
}
return result
}
// mergeSort 递归排序
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 main() {
arr := []int{10, 7, 8, 9, 1, 5}
fmt.Println("原数组:", arr)
sortedArr := mergeSort(arr)
fmt.Println("排序后的数组:", sortedArr)
}
代码说明：
merge 函数：用于合并两个有序数组。通过比较两个数组的元素，将较小的元素追加到结果数组中，直到一个数组为空。然后，将剩余的元素追加到结果数组中。
mergeSort 函数：递归排序函数。如果数组长度小于等于1，则返回该数组。否则，将数组分成两半，分别对两半进行递归排序，然后合并排序结果。
main 函数：定义一个待排序的数组 arr，调用 mergeSort 函数进行排序，最后打印排序前和排序后的数组。
归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)，适用于需要稳定排序且对空间复杂度要求不高的场景。
