【基础算法——分治思想】分治的五个基本实例：归并排序、快排、逆序对计数、最大子数组和、次序选择
package mainimport (
"fmt"
)//分治思想：归并排序
func MergeSort(arr []int, left int, right int) {
//递归边界
if left >= right {
return
}
//分解原问题
mid := (left + right)/2 //解决子问题
MergeSort(arr, left, mid)
MergeSort(arr, mid+1, right) //合并子问题的解得到原问题的解
Merge(arr, left, mid, right)
}//归并排序合并子问题的解
func Merge(arr []int, left int, mid int, right int){ tempArr := make([]int, right+1)
ptemp := left
pleft := left
pright := mid+1 for{if pleft > mid || pright > right {
break
}if arr[pleft] <= arr[pright] {
tempArr[ptemp] = arr[pleft]
pleft++
} else {
tempArr[ptemp] = arr[pright]
pright++
}ptemp++ } for ;
pleft<=mid;
pleft++ {
tempArr[ptemp] = arr[pleft]
ptemp++
} for ;
pright<=right;
pright++{
tempArr[ptemp] = arr[pright]
ptemp++
} for i:=left;
i<=right;
i++{
arr[i] = tempArr[i]
}}//分治思想：快排
func QuickSort(arr []int, left int, right int){ //递归边界
if left >= right {
return
} //分:寻找分界点 //以最右元素作为基准值
iqvt := arr[right]
//数组划分 使得pleft左面的数组元素均小于分界点元素的值，右面元素均大于基准值(Partition)
pleft := left-1
pright := left //开始进行数组划分
for ;
pright= right {
return 0
} //分-治
mid := (left + right)/2
n1 := ReverseCount(arr, left, mid)
n2 := ReverseCount(arr, mid+1, right) //合
n3 := CrossingCount(arr, left, mid, right)
n := n1 + n2 + n3
returnn
}//逆序对计数问题—过界逆序对计数
func CrossingCount(arr []int, left int, mid int, right int)int { count := 0
tempArr := make([]int, right+1)
ptemp := left
pleft := left
pright := mid+1 for ;
pleft<=mid && pright<=right;
{
if arr[pleft] <= arr[pright] {
tempArr[ptemp] = arr[pleft]for i:=mid+1;
i= right {
return arr[left]
} //分治
mid := (left + right)/2
s1 := MaxSum(arr, left, mid)
s2 := MaxSum(arr, mid+1, right) //合
s3 := MaxCrossing(arr, left, mid, right)
max := Max(s1, s2, s3)
return max
}func Max(s1 int, s2 int, s3 int) int {
max := s1
if s2 > max {
max = s2
} if s3 > max {
max = s3
} return max
}func MaxCrossing(arr []int, left int, mid int, right int)int{ //求左边以mid结尾的最大子数组和 右边以mid+1开头的最大子数组和 加起来就是crossMax值 //MaxLeftArry
maxleft := arr[mid]
sumleft := arr[mid]
for i:=mid-1;
i>=left;
i-- {
sumleft := sumleft + arr[i]
if sumleft > maxleft {
maxleft = sumleft
}
} //MaxRightArry
maxright := arr[mid+1]
sumright := arr[mid+1]
for i:=mid+2;
i<=right;
i++ {
sumright := sumright + arr[i]
if sumright > maxright {
maxright = sumright
}
} return maxright+maxleft
}//分治思想：次序选择问题(寻找第K小的元素)
func Select(arr []int, left int, right int, k int)int{ //递归边界
if k > right+1 {
return -1
} //就是找落在k-1坐标上的元素并返回
pivot := arr[right] //基准元素
pleft := left-1
pright := left //Partition
for ;
pright 
