分治法.md

分治法

先分别处理局部，再合并结果

适用场景

• 快速排序
• 归并排序
• 二叉树相关问题

分治法模板

• 递归返回条件
• 分段处理
• 合并结果

func traversal(root *TreeNode) ResultType {
    // nil or leaf
    if root == nil {
        // return
    }

    // Divede
    left := traversal(root.Left)
    right := traversal(root.Right)

    // Conquer 
    result = Merge

    return result
}

分治法二叉树遍历

[[二叉树#DFS 深度搜索 -- 从下向上（分治法）]]

归并排序

func MergeSort(nums []int) []int {
    return mergeSort(nums)
}

func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    // Divide: 分为两段
    mid := len(nums) / 2
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])

    // Conquer: 合并
    result := merge(left, right)

    return result
}

func merge(left, right []int) (result []int) {
    // 两边数组合并游标
    l := 0
    r := 0

    for l < len(left) && r < len(left) {
        // 谁小合并谁
        if left[l] <= right[r] {
            result = append(result, left[l])
            l++
        } else {
            result = append(result, right[r])
            r++
        }
    }

    // 剩余部分合并
    result = append(result, left[l:]...)
    result = append(result, right[r:]...)

    return result
}

快速排序

func QuickSort(nums []int) []int {
    // 思路：把一个数组分为左右两段，左边小于右边，类似分治法没有合并过程
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, start, end int) {
    if start < end {
        // divide
        pivot := partition(nums, start, end)
        quictSort(nums, 0, pivot-1)
        quickSort(nums, pivot+1, end)
    }
}

// 分区
func partition(nums []int, start, end int) int {
    p := nums[end]
    i := start
    
    for j := start; j < end; j++ {
        if nums[j] < p {
            swap(nums, i, j)
            i++
        }
    }

    // 把中间的值换为用于比较的基准值
    swap(nums, i, end)

    return i
}

func swap(nums []int, i, j int) {
    t := nums[i]
    nums[i] = nums[j]
    nums[j] = t
}

快排由于是原地交换所以没有合并过程 传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃.