这次我们介绍一下归并排序
一.归并排序
归并排序很好的体现了分治法的应用，排序的大致思路如下：
- 将数组切片为相同长度的两部分，一个是 nums[0...LEN/2] 另一个是 nums[LEN/2+1...LEN]
- 递归的对两个部分进行相同的切片操作，直到数组长度为1
- 对已经排好序的两个切片进行合并操作
简单解释一下上述思路，由于 1 的操作，我们已经将原数组切片为两个子数组，通过递归使用归并排序方法，子数组均已排序完成，我们接下来只需要将两个已经排好序的子数组进行合并即可
func merge_sort(start int, end int, nums string) string {
// 如何 start == end，也就是 nums 长度为1，直接返回该元素
// 我们可以认为长度为1的数组是已经排序好了的
if start == end {
return string(nums[start])
}
// 划分两个子数组
mid := (start + end) / 2
// 将低位数组排序
str1 := merge_sort(start, mid, nums)
// 将高位数组排序
str2 := merge_sort(mid+1, end, nums)
// 将两个有序数组合并
return merge(str1, str2)
}
func merge(str1 string, str2 string) string {
newString := ""
i := 0
j := 0
for i < len(str1) && j < len(str2) {
if str1[i] < str2[j] {
newString += string(str1[i])
i++
} else {
newString += string(str2[j])
j++
}
}
if i == len(str1) {
newString += string(str2[j:])
}
if j == len(str2) {
newString += string(str1[i:])
}
return newString
}
初次使用递归，会对递归的过程感到疑惑
我们可以追溯一下整个排序的过程
整个 nums长度为16，划分为两个数组 0~7和 8~15。
我们继续划分，将 0~7划分为 0~3和 4~7。 将 0~3继续划分为 0~1 和 2~3
如果我们继续划分，则最后的数组被划分为 0和 1
根据我们的代码和思路，此时直接返回单个元素
接着，我们合并两个单元素，也就是排序了的 M和 E，将其合并为 E和 M
同理，我们可以排序 R和 G，将其合并为 G和 R
接着，我们将 EM和GR进行合并，合并为 EGMR。此时 0~3的过程已经排序完成
回顾整个排序过程，我们将整个数组细分为一个一个的数字，然后两两之间进行合并，然后继续往上合并，最后将整个数组合并。合并过程就是我们的排序过程
接下来我们探讨一下归并排序的时间复杂度和稳定性
归并排序的过程主要消耗在将两个有序数组合并的过程上，整个归并排序的时间复杂度为 O(nlgn)，归并排序本身也是稳定的。
本次我们使用的是二路归并，几路归并取决于我们划分数组的数量，在本次介绍中，我们每次都将数组划分为两个子数组，所以叫做二路归并
