分治法三个步骤
分解：将原问题分解成一系列子问题；
解决：递归解决各个子问题，若子问题足够小，则直接求解子问题；
合并：将子问题的结果合并成原问题的解；
合并排序完全按照了上述模式
分解：将 n 个元素分成含 n / 2 个元素的子序列；
解决：用合并排序法对两个子序列递归排序；
合并：将两个子序列合并以得到已排序的结果；
合并排序过程
如图所示：
image.png
合并排序代码
func MergeSort(data []int, p int, r int) {
if p >= r {
return
}
q := p + (r-p)/2
MergeSort(data, p, q)
MergeSort(data, q+1, r)
merge(data, p, q, r)
}
func merge(data []int, p int, q int, r int) {
L := make([]int, q-p+1)
for i := p; i <= q; i++ {
L[i-p] = data[i]
}
L = append(L, math.MaxInt32) //为了不实时排到是否最后一个数字 添加一个哨兵
R := make([]int, r-q)
for i := q + 1; i <= r; i++ {
R[i-q-1] = data[i]
}
R = append(R, math.MaxInt32) //添加哨兵
i, j := 0, 0
for k := p; k <= r; k++ {
if L[i] < R[j] {
data[k] = L[i]
i++
} else {
data[k] = R[j]
j++
}
}
}
分治法算法分析
T(n) = O(1) 当n = 1
T(n) = aT(n/b) + D(n) +C(n) 当n>2
当n = 1时 只有一个元素 显然 T(n) = O(1)
当n>1时 D(n)表示分解问题 C(n) 表示合并问题
合并排序算法分析
假设不考虑n = 1的特征情况，O(1) < O(n) 其实也包含在T(n中)
在合并算法中 a = b = 2,分解与合并问题统一为cn
所以 T(n) = 2T(n/2)+cn
由于每次分解为1/2 假设一个2^n个元素分解情况如下：
image.png
由于每层时上层的1/2, 从cn到cn/2...c 高度应该是lgn。每次需要的时间为cn
所以 T(n) = cnlgn+cn
所以合并排序时间复杂度为 O(nlgn)
回顾分治法过程
分解：将原问题分解成一系列子问题；
解决：递归解决各个子问题，若子问题足够小，则直接求解子问题；
合并：将子问题的结果合并成原问题的解；
分治法时求解复杂问题的一种很好思路。
