常用算法实现【必会】：sort/bfs/dfs

常用排序算法实现（Go版本）

// 快排（分治）
// 时间复杂度：O(nlogn) 空间复杂度：O(logn)
func QuickSort(arr []int, left, right int) {var QuickSorting = func(arr []int, left, right int) int {tmp := arr[right] // 1、从右向左依次选基准值tmpfor left < right {for arr[left] <= tmp && left < right { // 2、每轮循环中先从左向右，遇到比基准值小的数则left++left++}if left < right {arr[right] = arr[left] // 3、直至遇到比基准值大的数x=array[left]为止，然后再交换基准值与较大值x的位置（保证基准值左侧的值都比基准值tmp小）}for arr[right] >= tmp && left < right { // 4、每轮循环中再从右向左，遇到比基准值大的数则right--right--}if left < right { // 5、直至遇到比基准值小的数y=array[right]为止，然后再交换基准值与较小值y的位置（保证基准值右侧的值都比基准值tmp大）arr[left] = arr[right]}}arr[left] = tmpreturn left}if left < right {mid := QuickSorting(arr, left, right)QuickSort(arr, left, mid-1)QuickSort(arr, mid+1, right)}
}// 快排（非递归）// todo:待补充
// https://www.bilibili.com/video/av758822583/?vd_source=2c268e25ffa1022b703ae0349e3659e4
func QuickSortNotByRecursion(arr []int) {
}// 堆排（大顶堆：每个节点的值都大于或等于其左右孩子节点的值）
// 时间复杂度：O(nlogn) 空间复杂度：O(1)
func HeapSort(arr []int) {var CreateHeap = func(arr []int, i, length int) {tmp := arr[i]// 注意for循环条件：是 j<length 而不是 j<len(arr)for j := 2*i + 1; j < length; j = j*2 + 1 { // j=2i+1:当前根节点的左孩子下标 j= 2*j + 1:以当前叶子节点为新根节点，该新根节点的下一层叶子节点左孩子下标if j+1 < length && arr[j] < arr[j+1] { // j+1<length:右孩子(j+1)不能超出len长度范围j++}if tmp > arr[j] { // 左右孩子节点中选较大的节点值，并与父节点比较大小break // 若父节点值满足"大于或等于其左右孩子节点的值"则break，否则与较大的孩子节点相互交换}arr[i] = arr[j]i = j}arr[i] = tmp // 将最终比较后较小值放到合适的位置}// 首次构建堆l := len(arr)for i := l / 2; i >= 0; i-- { // 从二叉树最后一个父节点从底向上遍历（最上面的父节点：i = 0；最后一个父节点下标：i = len(arr) / 2）CreateHeap(arr, i, l)}// 再次重建堆for i := l - 1; i > 0; i-- { // 从下往上不断在每轮循环中置换出当前最大值，arr长度i也逐渐减到0arr[0], arr[i] = arr[i], arr[0] // swap 把大顶堆根节点(下标为0)上的最大值交换到末尾，置换出来.CreateHeap(arr, 0, i)}
}// 归并
// 时间复杂度：O(nlogn) 空间复杂度：O(n)
func MergeSort(arr []int, length int) {var MergeSorting = func(arr1, arr2 []int, length1, length2 int) {i, j := 0, 0tempArr := make([]int, 0 /*, length1+length2*/)// 1.分别将两个子数组中较小一方的值按大小顺序移动到临时数组tempArr中for i < length1 && j < length2 {if arr1[i] < arr2[j] {tempArr = append(tempArr, arr1[i]) // 将较小值加入临时数组tempArri++// fmt.Println("i ", i)} else {tempArr = append(tempArr, arr2[j])j++// fmt.Println("j ", j)}}// 2.肯定存在一个子数组先移动完，所以需要将另一个未移动完的有序子数组剩下的元素继续移动到tempArr中if i < length1 {tmpArr = append(tmpArr, arr1[i:]...)}if j < length2 {tmpArr = append(tmpArr, arr2[j:]...)}// 3.将合并数组值赋给原始数组copy(arr, tmpArr) // arr = tempArr // 此赋值方式不会影响main()中原数组arr中的值，仅仅在该函数作用域内的结果是排好序的// for i := 0; i < length1+length2; i++ {// 	arr[i] = tmpArr[i]// }}// 注意：下面的l1和l2不能写成 "len(arr)/2" 和 "len(arr)-l1"if length > 1 { // 最后拆至每个子数组只有一个元素l1 := length / 2l2 := length - l1arr1, arr2 := arr, arr[l1:] // arr1原数组前半部分、arr2原数组后半部分MergeSort(arr1, l1)         // 不断拆分数组长度直至长度为1MergeSort(arr2, l2)         // 不断拆分数组长度直至长度为1MergeSorting(arr1, arr2, l1, l2)// mid := length / 2// arr1, arr2 := arr[:mid], arr[mid:] // arr1原数组前半部分、arr2原数组后半部分// MergeSort(arr1, len(arr1))         // 不断拆分数组长度直至长度为1// MergeSort(arr2, len(arr2))         // 不断拆分数组长度直至长度为1// MergeSorting(arr1, arr2, len(arr1), len(arr2))}
}// 冒泡
// 时间复杂度：O(n^2) 空间复杂度：O(1)
func MaoPaoSort(arr []int) {for i := 0; i < len(arr); i++ {for j := i + 1; j < len(arr); j++ {if arr[i] > arr[j] {arr[i], arr[j] = arr[j], arr[i] // swap}}}
}func main() {array := []int{5, 28, 73, 19, 6, 0, 5}// MaoPaoSort(array)// QuickSort(array, 0, len(array)-1)// QuickSortNotByRecursion(array)// HeapSort(array)MergeSort(array, len(array))fmt.Println(array)return
}

---

BFS 广度优先遍历，利用queue

// BFS（利用队列：尾进头出）
func levelOrder(root *TreeNode) []int {res := make([]int, 0)if  root == nil {   return res}queue := []*TreeNode{root} // 开始循环前，先塞入rootfor len(queue) > 0 {root = queue[0] // 获取即将出队的头节点res = append(res, root.Val)queue = queue[1:] // 头结点出队if root.Left != nil {queue = append(queue, root.Left)}if root.Right != nil {queue = append(queue, root.Right)}}return res
}

---

DFS 深度优先遍历，利用stack

前序遍历（根 左 右）

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
// 迭代
func preorderTraversal(root *TreeNode) []int {array := make([]int, 0)stack := make([]*TreeNode, 0)for root != nil || len(stack) > 0 {// 不断遍历左子树for root != nil {array = append(array, root.Val) // result, finally return stack = append(stack, root)     // pushroot = root.Left}// 左子树遍历完了，开始从下往上遍历右子树（每次找栈顶指针，然后pop出栈）if len(stack) > 0 {root = stack[len(stack) - 1]    // 获取栈顶元素root = root.Rightstack = stack[: len(stack) - 1] // pop}}return array
}// 递归
var array []int
func preorderTraversal(root *TreeNode) []int {array = make([]int, 0)dfs(root)return array
}func dfs(root *TreeNode) {if root == nil {return}array = append(array, root.Val)dfs(root.Left)dfs(root.Right)
} 

中序遍历（左根右）

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/// 迭代
func inorderTraversal(root *TreeNode) []int {res := make([]int, 0)stack := make([]*TreeNode, 0)for root != nil || len(stack) > 0 {for root != nil {stack = append(stack, root)root = root.Left}if len(stack) > 0 {top := stack[len(stack) - 1]res = append(res, top.Val)root = top.Rightstack = stack[:len(stack) - 1] // pop}}return res
}// 递归
func inorderTraversal(root *TreeNode) []int {res := make([]int, 0)var inorder func(root *TreeNode)inorder = func(root *TreeNode) {if root != nil {inorder(root.Left)res = append(res, root.Val)inorder(root.Right)}}inorder(root)return res
}

后序遍历（左 右 根）

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/// 迭代
// https://github.com/HelloWorld-666/C_Tree/blob/master/C_Tree/main.cpp
// 每个节点会经过两次栈，第一次不断遍历左子节点会经过，第二次遍历完右子节点后，获取栈顶节点时也会经过；
// 且当某个根节点root左右孩子节点都为空时，root出栈并置空
func postorderTraversal(root *TreeNode) []int {res := make([]int, 0)stack:= make([]*TreeNode, 0)flagMap := make(map[*TreeNode]int)          // 标记节点是第几次经过根节点 => 入栈for root != nil || len(stack) > 0 {for root != nil {                       // 遍历左子节点stack = append(stack, root)         // pushflagMap[root] = 1                   // 第1次经过该节点时，做标记:1root = root.Left}if len(stack) > 0 {root = stack[len(stack) - 1]        // 获取栈顶节点if flagMap[root] == 1 {flagMap[root] = 2               // 第2次经过该节点时，做标记:2root = root.Right} else {res = append(res, root.Val)stack = stack[:len(stack) - 1]  // pop stack top noderoot = nil // 当前root的左右子节点都为空时(叶子节点)，将该root出栈且置空，避免该root因不等于空而再次进入上方内循环中逻辑.}}}return res
}// 递归
func postorderTraversal(root *TreeNode) []int {res := make([]int, 0)var recursion func(root *TreeNode)recursion = func(root *TreeNode) {if root != nil {recursion(root.Left)recursion(root.Right)res = append(res, root.Val)}}recursion(root)return res
}

BFS/DFS 总结

将所有结点都看作根结点，关键在于何时访问。
前序：入栈时访问；中序：第一次退栈时访问；后序：第二次退栈时访问。

深度优先遍历（借助栈stack结构来实现） = 前中后序遍历
dfs:一条路走的死,用栈实现,进栈、退栈，一搜到底!一般用 递归 实现
bfs: 辐射八方,用队实现,入队、出队，步步为营!一般用 迭代 实现
深度优先，就是 一条路走到底，广度优先，就是 每条路都同时派人走 。

另外：删除一棵二叉树，即释放一棵二叉树的内存，用后序遍历即可实现（这里的“访问”变成了delete 结点）.