介绍
归并排序（Merge Sort）是一种经典的排序算法，它采用分治（Divide and Conquer）的策略来进行排序。它将待排序的数组逐步地划分为较小的子数组，然后对这些子数组进行排序，最后将排序好的子数组合并成一个有序的数组。
归并排序的基本思想如下：
- 分解：将待排序的数组递归地分解为较小的子数组，直到每个子数组只包含一个元素或为空。
- 解决：对每个子数组进行排序。当子数组的长度为 1 时，认为它是已排序的。
- 合并：将两个有序的子数组合并成一个有序的数组。重复这个过程，直到最终合并成一个完整的有序数组。
归并排序的关键步骤是合并操作。合并操作的基本过程如下：
- 创建一个临时数组或列表，用于存储合并后的结果。
- 初始化两个指针，分别指向两个有序子数组（左子数组和右子数组）的起始位置。
- 比较两个指针所指向的元素，将较小的元素放入临时数组，并将相应的指针向后移动一位。
- 重复上述步骤，直到其中一个子数组的元素全部被合并。
- 将剩余子数组的所有元素直接追加到临时数组的末尾。
- 将临时数组中的元素复制回原始数组的相应位置，完成合并。
归并排序是一种稳定的排序算法，具有较好的时间复杂度，适用于大规模数据的排序。但需要注意的是，归并排序在实际应用中可能需要较大的额外空间，因此在空间受限的情况下需要考虑其他排序算法。
代码示例
package main
import "fmt"
func mergeSorted(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
//fmt.Println("mid: ", mid)
left := mergeSorted(arr[:mid])
//fmt.Println("left: ", left)
right := mergeSorted(arr[mid:])
//fmt.Println("right: ", right)
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:]...)
//fmt.Println("1: ", result)
result = append(result, right[j:]...)
//fmt.Println("2: ", result)
return result
}
func main() {
arr := []int{3, 5, 1, 2, 4}
fmt.Println(arr)
fmt.Println(mergeSorted(arr))
}
代码解释
- 如果输入的数组长度小于等于 1，直接返回该数组，因为一个元素或者空数组本身就是有序的。
- 计算数组的中间位置 mid。
- 递归调用 mergeSort 函数对左半部分数组 arr[:mid] 进行排序，得到有序的 left 数组。
- 递归调用 mergeSort 函数对右半部分数组 arr[mid:] 进行排序，得到有序的 right 数组。
- 调用 merge 函数将两个有序的数组 left 和 right 合并成一个有序的结果数组 result。
- 创建一个空的切片 result 用于存储合并后的结果。
- 使用两个指针 i 和 j 分别指向 left 和 right 数组的起始位置。
- 比较 left[i] 和 right[j] 的大小，将较小的元素追加到 result 中，并将相应的指针向后移动一位。
- 重复上述步骤，直到遍历完其中一个数组。
- 将左侧子数组 left 中从索引 i 到末尾的所有元素追加到 result 数组的末尾。… 表示将切片 left[i:] 展开为独立的元素，然后使用 append 函数将这些元素追加到 result 数组中。将右侧子数组 right 中从索引 j 到末尾的所有元素追加到 result 数组的末尾。
- 返回合并后的结果数组 result。
运行结果
- [3 5 1 2 4]
- mid: 2
- mid: 1
- left: [3]
- right: [5]
- left: [3 5]
- mid: 1
- left: [1]
- mid: 1
- left: [2]
- right: [4]
- right: [2 4]
- right: [1 2 4]
- [1 2 3 4 5]
复杂度
时间复杂度：
最好情况、最坏情况和平均情况下，归并排序的时间复杂度都是 O(n log n)，其中 n 是待排序数组的长度。归并排序的时间复杂度是稳定的，不受输入数据的影响。
空间复杂度：
归并排序的空间复杂度是 O(n)，其中 n 是待排序数组的长度。在合并过程中，需要额外的空间来存储临时数组，以及递归调用时的函数调用栈。