归并排序

我们呢下面介绍一下递归的几个使用的场景这个里面不会介绍像这个斐波那契数列那样的递归就是数学函数很容易理解我们就拿数据结构里面的排序算法和二叉树的遍历作为例子熟悉一下这个过程

我们这个地方是以后序遍历作为例子。

对于一个二叉树而言这个后序遍历的时候我们先遍历根节点的左子树再去遍历根节点的右子树。

最后遍历这个根节点

在遍历左子树的时候我们要先遍历这个左子树的根节点的左子树再去遍历这个左子树根节点的右子树以此类推对于任何一个子树我们都会先遍历这个根节点的左子树再去遍历这个根节点的右子树

1.2快速排序

快速排序和下面介绍的这个归并排序对于初学者而言很相似我就是这个感觉但是两个排序算法还是有很多的差异的

快速排序之所以敢这么叫这个名字自身的这个时间消耗上面肯定是可以的它是有使用价值的并不想其他的一些排序算法只有教学意义没有实践意义

快排需要先确定一个基准元素把小于这个元素的放到左边大于这个元素的放到右边分别对于这个左边的和右边的进行排序还是选择基准元素按照上面的方法进行下去

1.3归并排序

归并排序就和上面的快速排序有点不同了因为归并排序是直接从中间分开然后再把这个自己左右分开直到分成一个一个的元素最后把这个元素有序的组合起来即可

下面的这个就是归并排序的过程展示就是分开之后合并的过程这个合并的时候我们是使用的双指针的方法合并的通过指针的移动

2.为什么会用到递归

我们在解决一个问题的时候把这个问题分解为诸多的子问题可以使用一个方法解决这个主问题但是解决子问题的时候同样可以使用这个方法解决

3.如何理解递归

3.1递归展开细节图这个是初学的时候老师经常搞的一种方法但是这个并不一定会简化我们对于这个递归问题的理解

3.2二叉树的题目我们在二叉树学习的时候尤其是涉及到这个二叉树的遍历因为二叉树的遍历里面遍历任何一个子树的方法都是一样的他们都是若干个子问题我们就可以直接使用递归解决这个问题

3.3宏观看待递归过程我们跳出上面的递归细节展开图找准子问题只需要关注一个问题的实现再去套用这个方法解决其他的问题

我们没有实现但是我们先把这个root-left作为函数的参数root-right作为函数的参数最后判断这个结束条件到达叶子结点就结束

void

NULL){return;}dfs(root-left);dfs(root-right);printf(%d,

root-val);

我们先计算这个mid值大小再把这个mid作为参数传递进去分别传递这个左边区间和右边区间使用这个函数进行排序最后合并两个有序数组结束条件就是leftright,结束递归的过程

void

4.1函数头的书写找到一个主问题里面的字问题看看是否可以使用相同的方法解决子问题

5.1深度dfs优先遍历优先搜索

深度就是一条路走到尽头之后再去折返回去这个里面遍历只是过程的一种形式搜索才是真正想要达到的目的

5.2宽度bfs优先遍历优先搜索

宽度就是你一层一层的进行按照这个二叉树的层状结构进行遍历这一层结束之后进行下一层

6.回溯

回溯就是深度搜索我们可以举例一下这个走迷宫的问题帮助我们理解一下当我们走到一个迷宫的某一个节点的时候我们有多个选择我们肯定是只能走其中的一条这个时候我们认准一条路并且总下去这个时候我们发现走到了死胡同这个时候我们就需要则返回那个岔路口这个从现在所在位置返回到刚刚做选择的岔路口就是一个回溯的过程因此我们说这个回溯和深度搜索没有什么本质的区别都是一条路走到黑再去选择另外的一条路仅此而已。