NarcissusBlog分治算法
分治算法可以认为是一种算法思想，通过将原问题分解成小规模的子问题，然后根据子问题的结果构造出原问题的答案。
归并排序
归并排序是最典型的分治算法。要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
1、原地归并
实现归并一种直接了当的方法就是将两个不同的有序数组归并到第三个数组中。但是当用归并将一个大数组排序时，需要多次归并，每次都用新数组会带来问题和巨大的空间开销。因此需要原地归并的方式，在数组中移动元素而不使用额外的空间。
merge(a []int, lo, mid, hi int)方法会将子数组a[lo..mid]和a[mid+1..hi]归并成一个有序的数组并将结果放在a[lo..hi]中。
方法先将所有元素复制到aux[]中，然后再归并到a[]中。第二个for循环中进行了4个条件判断：左半边用尽（取右半边的元素）、右半边用尽（取左半边的元素）、右半边的当前元素小于左半边的当前元素（取右半边的元素）以及右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。
注意：为什么不把数组
aux[]声明为merge()方法的局部变量?这是为了避免每次归并时，即使归并很小的数组，都创建一个新数组。如果这样做，那么创建新数组将成为归并排序运行时间的主要部分。因此，好的方式是将临时数组
aux[]作为参数传入，在调用排序的函数中进行声明(分配空间和待排序数组一样长)或者声明在结构体中。
2、自顶向下的归并排序
要对子数组a[lo..hi]进行排序，先将它分为a[lo..mid]和a[mid+1..hi]两部分，分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。代码如下：
func sort(a, aux []int, lo, hi int) {
if hi <= lo {
return
}
mid := lo + (hi - lo) >> 1
// 分：对数组两个部分分别排序
sort(a, aux, lo, mid)
sort(a, aux, mid+1, hi)
// 治：合并两个排序好的子数组
merge(a, aux, lo, mid, hi)
}
func merge(a, aux []int, lo, mid, hi int) {
// 将a[lo..mid] 和 a[mid+1..hi] 归并
i, j := lo, mid + 1
// 将a[lo..hi]复制到aux[lo..hi]
for k := lo; k <= hi; k++ {
aux[k] = a[k]
}
// 归并回到a[lo..hi]
for k := lo; k <= hi; k++ {
if i > mid {
a[k] = aux[j]
j++
} else if j > hi {
a[k] = aux[i]
i++
} else if aux[j] < aux[i] {
a[k] = aux[j]
j++
} else {
a[k] = aux[i]
i++
}
}
}
如下图所示，为数组 [7, 3, 2, 6, 0, 1, 5, 4]的归并排序过程。
3、自底向上的归并排序
这种方式是先成对归并微型数组，直到将整个数组归并在一起。代码如下：
func sort(a, aux []int, lo, hi int) {
// 进行lgN次两两归并
N := len(a)
// sz子数组大小
for sz := 1; sz < N; sz = sz + sz {
// lo子数组索引
for lo := 0; lo < N - sz; lo += sz + sz {
merge(a, aux, lo, lo + sz - 1, min(lo + sz + sz - 1, N - 1))
}
}
}
func merge(a, aux []int, lo, mid, hi int) {
// 将a[lo..mid] 和 a[mid+1..hi] 归并
i, j := lo, mid + 1
// 将a[lo..hi]复制到aux[lo..hi]
for k := lo; k <= hi; k++ {
aux[k] = a[k]
}
// 归并回到a[lo..hi]
for k := lo; k <= hi; k++ {
if i > mid {
a[k] = aux[j]
j++
} else if j > hi {
a[k] = aux[i]
i++
} else if aux[j] < aux[i] {
a[k] = aux[j]
j++
} else {
a[k] = aux[i]
i++
}
}
}
数组中的逆序对
归并排序和逆序对是息息相关的。在归并过程中统计逆序对的数量，如下图所示，为数组 [7, 3, 2, 6, 0, 1, 5, 4]的归并排序与逆序对统计过程。
代码如下：
func reversePairs(nums []int) int {
aux := make([]int, len(nums))
var sort func(nums, aux []int, lo, hi int, result *int)
sort = func(nums, aux []int, lo, hi int, result *int) {
if hi <= lo {
return
}
mid := lo + (hi - lo) >> 1
sort(nums, aux, lo, mid, result)
sort(nums, aux, mid + 1, hi, result)
merge(nums, aux, lo, mid, hi, result)
}
lo, hi := 0, len(nums) - 1
result := 0
sort(nums, aux, lo, hi, &result)
return result
}
func merge(nums, aux []int, lo, mid, hi int, result *int) {
// 将nums[lo..hi]复制到aux数组
for k := lo; k <= hi; k++ {
aux[k] = nums[k]
}
i, j := lo, mid + 1
for k := lo; k <= hi; k++ {
if i > mid {
nums[k] = aux[j]
j++
} else if j > hi {
nums[k] = aux[i]
i++
} else if aux[i] > aux[j] {
nums[k] = aux[j]
j++
// 统计逆序对
*result += mid - i + 1
} else {
nums[k] = aux[i]
i++
}
}
}