3-2归并排序法的实现,递归不是很理解,您说_mergeSort(arr,l,mid)这样递归后里面就左半部分就排好序了,这是不可能的啊

Answer 1

liuyubobobo 2018-02-23 16:11:32

__mergeSort在最初会不断的细分整个数组，当数组的长度为1，即整个数组不需要排序也是有序的情况下开始进行__merge，将两个包含有1个元素的数组merge成了一个有序的2个元素的数组；之后将两个有序的包含2个元素的数组合并成一个有序的包含4个元素的数组；之后将两个有序的包含4个元素的数组合并成一个有序的包含8个元素的数组...依次类推。

这里有个重点，需要体会：递归函数执行完以后是要返回上层继续执行的。其实递归函数的调用和普通函数的调用没有区别。普通函数的调用中，A函数里执行B，B执行完以后将继续执行A。递归函数也是一样的。在A函数里执行A，这个A执行完以后，要返回到上层继续执行上层的A。

如果对这个过程的细节感觉理解的还不透彻，不要只对着代码生想。实际使用一个小数据量的测试用例，比如只包含8个元素的无序数组，然后使用debug一步一步跟着程序走一遍，观察程序在运行每一行代码之后数据和各种辅助的变量具体是怎样变化的，看看和自己的理解是否有偏差。这是非常好的理解算法运行机制的形式。千万不要怕麻烦！踏踏实实拿一张纸一根笔，找一个下午做一遍这个事情，是绝对值得的。

加油！

• 提问者 慕标1012604 #1

  你好，老师。还想问一个问题，您是如何将这种抽象问题用代码实现的，最开始就一下子想到递归么。

• liuyubobobo 回复 提问者 慕标1012604 #2

  初学者对递归理解的不深刻，肯定是不能一下子把这种思想付诸到递归实现中的。其实这也是我们学习经典算法的目的：经典算法背后蕴含着经典的算法思维方式，见到用类似的思路解决的问题多了，久而久之，自然可以灵活地运用这种思维方式到新的问题中去。是的，我见到类似的问题，一下子就能想到用递归去实现。但这是基于我已经见到太多各种使用递归解决的问题。个人建议，在学习经典算法的过程中，不要想太多“为什么这么做”，或者至少先不要想太多“为什么这么做”。先把到底是怎样做才能够正确解决这个问题学懂。换句话说，先别想太多为什么归并排序要用递归实现。先踏踏实实地把归并排序代码执行的逻辑理清楚，搞清楚为什么这样的逻辑可以正确的进行排序。见多了，有一天回头看，你会发现这个思维是很自然的：）