海口模板建站公司,用手机制作图片的app,爱站网反链分析,html5网站制作培训文章目录常用排序算法实现#xff08;Go版本#xff09;BFS 广度优先遍历#xff0c;利用queueDFS 深度优先遍历#xff0c;利用stack前序遍历#xff08;根 左 右#xff09;中序遍历#xff08;左根右#xff09;后序遍历#xff08;左 右 根#xff09;BFS/DFS 总…
文章目录常用排序算法实现Go版本BFS 广度优先遍历利用queueDFS 深度优先遍历利用stack前序遍历根 左 右中序遍历左根右后序遍历左 右 根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、每轮循环中先从左向右遇到比基准值小的数则leftleft}if left right {arr[right] arr[left] // 3、直至遇到比基准值大的数xarray[left]为止然后再交换基准值与较大值x的位置保证基准值左侧的值都比基准值tmp小}for arr[right] tmp left right { // 4、每轮循环中再从右向左遇到比基准值大的数则right--right--}if left right { // 5、直至遇到比基准值小的数yarray[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, mid1, right)}
}// 快排非递归// todo:待补充
// https://www.bilibili.com/video/av758822583/?vd_source2c268e25ffa1022b703ae0349e3659e4
func QuickSortNotByRecursion(arr []int) {
}// 堆排大顶堆每个节点的值都大于或等于其左右孩子节点的值
// 时间复杂度O(nlogn) 空间复杂度O(1)
func HeapSort(arr []int) {var CreateHeap func(arr []int, i, length int) {tmp : arr[i]// 注意for循环条件是 jlength 而不是 jlen(arr)for j : 2*i 1; j length; j j*2 1 { // j2i1:当前根节点的左孩子下标 j 2*j 1:以当前叶子节点为新根节点该新根节点的下一层叶子节点左孩子下标if j1 length arr[j] arr[j1] { // j1length:右孩子(j1)不能超出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) / 2CreateHeap(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 /*, length1length2*/)// 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 length1length2; i {// arr[i] tmpArr[i]// }}// 注意下面的l1和l2不能写成 len(arr)/2 和 len(arr)-l1if 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 结点.
