思想
先分别处理局部，再合并结果。分而治之。
使用场景：
- 快速排序
- 归并排序
- 二叉树相关问题
分治法模板
- 递归返回条件
- 分段处理
- 合并结果
func traversal(root *TreeNode) ResultType { // nil or leaf if root == nil { // do something and return } // Divide ResultType left = traversal(root.Left) ResultType right = traversal(root.Right) // Conquer ResultType result = Merge from left and right return 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) / 2 left := mergeSort(nums[:mid]) right := mergeSort(nums[mid:]) // 合并两段数据 result := merge(left, right) return result } func merge(left, right []int) (result []int) { // 两边数组合并游标 l := 0 r := 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 { // 分治法：divide pivot := 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 := 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 }
堆排
package main func 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] }
十大经典排序算法
十大经典排序算法（动图演示）
