基礎算法——分治思想

分治的五個基本執行個體：歸并排序、快排、逆序對計數、最大子數組和、次序選擇

package main

import (
	"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; pright++ {
		if arr[pright] < iqvt{
			temp := arr[pright]
			arr[pright] = arr[pleft+1]
			arr[pleft+1] = temp
			pleft++
		}

	}
	arr[pright] = arr[pleft+1]
	arr[pleft+1] = iqvt

	//數組劃分結束 此時iqvt完成了排序 坐标值為mid
	mid := pleft+1

	//治：解決子問題
	QuickSort(arr, left, mid-1)
	QuickSort(arr, mid+1, right)
}



//分治思想：逆序對計數問題
func ReverseCount(arr []int, left int, right int) int{
	//遞歸邊界
	if left >= 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
	return  n
}

//逆序對計數問題—過界逆序對計數
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<pright; i++ {
				fmt.Println("reverse: ", arr[pleft], "——", arr[i])
			}
			count = count + pright - (mid+1)
			pleft++
		} else {
			tempArr[ptemp] =arr[pright]
			pright++
		}
		ptemp++
	}

	for ; pleft<=mid; pleft++ {
		tempArr[ptemp] = arr[pleft]

		for i:=mid+1; i<=right; i++ {
			fmt.Println("reverse: ", arr[pleft], "——", arr[i])
		}

		count = count + right - mid

		ptemp++
	}

	for ; pright<=right; pright++ {
		tempArr[ptemp] = arr[pright]
		ptemp++
	}

	for i:=left; i<=right; i++ {
		arr[i] = tempArr[i]
	}
	return count
}

//分治思想：最大子數組問題
func MaxSum(arr []int, left int, right int)  int{

	//遞歸邊界
	if left >= 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<right; pright++ {
		if arr[pright] < pivot {
			temp := arr[pright]
			arr[pright] = arr[pleft+1]
			arr[pleft+1] = temp
			pleft++
		}
	}
	arr[right] = arr[pleft+1]
	arr[pleft+1] = pivot

	//此時确定了pivot元素排好序的位置 下标為pleft+1
	mid := pleft+1
	if mid == k-1 {
		return pivot
	} else if mid < k-1 {
		return Select(arr, mid+1, right, k)
	} else {
		return Select(arr, left, mid-1, k)
	}

}




func main() {


	//歸并排序
	arr1 := []int{-500,10,5,5,2,-3,-29,-10,-50,22,-23,10,150,1,9,-900,-26,3,99,7}
	MergeSort(arr1,0, len(arr1)-1)
	fmt.Println("MergeSort Result：")
	for _,v := range arr1{
		fmt.Printf("%d, ", v)
	}
	fmt.Print("\n")

	//快速排序
	arr2 := []int{-500,10,5,5,2,-3,-29,-10,-50,22,-23,10,150,1,9,-900,-26,3,99,7}
	QuickSort(arr2, 0, len(arr2)-1)
	fmt.Println("QuickSort Result：")
	for _,v := range arr2{
		fmt.Printf("%d, ", v)
	}
	fmt.Print("\n")

	//逆序對計數問題
	fmt.Println("ReverseCount Result：")
	arr3 := []int{-500,10,5,5,2,-3,-29,-10,-50,22,-23,10,150,1,9,-900,-26,3,99,7}
	count := ReverseCount(arr3, 0, len(arr3)-1)
	for _,v := range arr3{
		fmt.Printf("%d, ", v)
	}
	fmt.Println("")
	fmt.Printf("逆序對的個數為%d\n", count)

	//最大子數組和
	arr4 := []int{-500,10,5,5,2,-3,-29,-10,-50,22,-23,10,150,1,9,-900,-26,3,99,7}
	maxSum := MaxSum(arr4, 0, len(arr4)-1)
	fmt.Println("MaxSum Result: ")
	fmt.Println("最大子數組和為", maxSum)

	//次序選擇問題
	arr5 := []int{-500,10,5,5,2,-3,-29,-10,-50,22,-23,10,150,1,9,-900,-26,3,99,7}
	k := 6
	elem := Select(arr5, 0, len(arr5)-1, 3)
	fmt.Println("Select Orderer:")
	fmt.Printf("第%d小的數為%d\n", k, elem)
}