归并排序算法过程图解 为什么归并排序merge sort不需要像动态规划的问题一样考虑每一种划分情况？
为什么归并排序merge sort不需要像动态规划的问题一样考虑每一种划分情况？
针对你的问题：
为什么归并排序merge sort不需要像动态规划的问题一样考虑每一种划分情况？
我的分析如下：
递归的重要性不言而喻，它是很多算法实现的基础，比如含有分治思想的算法（归并排序，二分查找），有关遍历二叉树的算法，或者求解数学递推式的算法（斐波那契数列，n的阶乘），回溯法，动态规划等等， 一提到递归总有点发蒙，理论上比较好理解，但是一遇到复杂一点的递归算法，在大脑中很难想象递归在计算机中是怎么实现的。跟着一步步debug才终于搞明白，所以在这里先把过程给记录下来。
归并排序算法：就是运用分治的思想，把排序的过程变为先把数组分成左右两个部分，分别排序，再将排好序的两个数组合并成一个有序数组。
重点分析一下代码中 Merge_sort_c这个递归函数，首先是终止条件p>=r ，递归必须要有终止条件，否则就会陷入循环最终导致栈溢出。为啥会栈溢出？递归调用在底层其实是对线程栈的压栈和出栈操作，每调用一次都会压栈一次，并记录相关的局部变量信息，线程栈的内存是非常有限的，而递归调用如果是无限的，那么很快就会消耗完所有的内存资源，最终导致内存溢出。
接下来是两个调用了Merge_sort_c 函数本身也就是递归调用，将这两个递归调用分别编号#1和#2.在本例中，待排序的数组里面有6个元素(下标0-5)， 那么他们是怎么被压栈又出栈的呢？如下图所示:
合并排序和归并排序是同一种排序方法吗？
归并排序是一种稳定的算法（即在排序过程中大小相同的元素能够保持排序前的顺序，3212升序排序结果是1223，排序前后两个2的顺序不变），这一点在某些场景下至关重要。 归并排序是最常用的外部排序方法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序）。 归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分”与“合”的工作，并不是先“分”完再“合”（“分”很简单，不就是一直二分二分直到不可再分呗，额，这么想就错了，分完就合不起来了，切记“分”与“合”是结合在一起的）
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
