思想

先分别处理局部，再合并结果。分而治之。
使用场景：

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

分治法模板

1. 递归返回条件
2. 分段处理
3. 合并结果

func traversal(root *TreeNode) ResultType  {// nil or leafif root == nil {// do something and return}// DivideResultType left = traversal(root.Left)ResultType right = traversal(root.Right)// ConquerResultType result = Merge from left and rightreturn result
}

分治法遍历二叉树

func preorderTraversal(root *TreeNode) []int {result := divideAndConquer(root)return result
}
func divideAndConquer(root *TreeNode) []int {result := make([]int, 0)// 返回条件(null & leaf)if root == nil {return result}// 分治(Divide)left := divideAndConquer(root.Left)right := divideAndConquer(root.Right)// 合并结果(Conquer)result = append(result, root.Val)result = append(result, left...)result = append(result, right...)return result
}

归并排序

func MergeSort(nums []int) []int {return mergeSort(nums)
}
func mergeSort(nums []int) []int {if len(nums) <= 1 {return nums}// 分治法：divide 分为两段mid := len(nums) / 2left := mergeSort(nums[:mid])right := mergeSort(nums[mid:])// 合并两段数据result := merge(left, right)return result
}
func merge(left, right []int) (result []int) {// 两边数组合并游标l := 0r := 0// 注意不能越界for l < len(left) && r < len(right) {// 谁小合并谁if left[l] > right[r] {result = append(result, right[r])r++} else {result = append(result, left[l])l++}}// 剩余部分合并result = append(result, left[l:]...)result = append(result, right[r:]...)return
}

快排

func QuickSort(nums []int) []int {// 思路：把一个数组分为左右两段，左段小于右段，类似分治法没有合并过程quickSort(nums, 0, len(nums)-1)return nums}
// 原地交换，所以传入交换索引
func quickSort(nums []int, start, end int) {if start < end {// 分治法：dividepivot := partition(nums, start, end)quickSort(nums, 0, pivot-1)quickSort(nums, pivot+1, end)}
}
// 分区
func partition(nums []int, start, end int) int {p := nums[end]i := startfor 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
}

堆排

package mainfunc HeapSort(a []int) []int {//将无序数组a构建为一个大根堆for i := len(a)/2 - 1; i >= 0; i-- {sink(a, i, len(a))}// 然后把前面这段数组继续下沉保持堆结构，如此循环即可for i := len(a) - 1; i >= 1; i-- {// 从后往前把数组变有序swap(a, 0, i)// 前面的长度减一,因为最后一个是有序的sink(a, 0, i)}return a
}
func sink(a []int, i int, length int) {for {// 左节点索引(从0开始，所以左节点为i*2+1)l := i*2 + 1// 右节点索引r := i*2 + 2// idx保存根、左、右三者之间较大值的索引idx := i// 存在左节点，左节点值较大，则取左节点if l < length && a[l] > a[idx] {idx = l}// 存在右节点，且值较大，取右节点if r < length && a[r] > a[idx] {idx = r}// 如果根节点较大，则不用下沉if idx == i {break}// 如果根节点较小，则交换值，并继续下沉swap(a, i, idx)// 继续下沉idx节点i = idx}
}
func swap(a []int, i, j int) {a[i], a[j] = a[j], a[i]
}

十大经典排序算法

十大经典排序算法（动图演示）