2 u011456891 u011456891 于 2014.12.01 22:07 提问

排序的递归问题:能否用函数指针以及栈代替递归??

最近学习排序,对于快排,归并等处理海量数据效率高的算法很钟意,但是其自身的递归特性有很多缺点,譬如数据量过大时存在溢出的风险,也影响了算法的效率,故想到用栈代替递归这一过程。大致想法就是创建个函数指针类型的栈,然后将每个子排序的函数指针压入其中,然后再一个一个用*解引用来运行函数。当然我知道改成非递归有别的方法,但是可能会比这复杂,就想考虑用栈来实现。我想知道的是,对于快排和归并等递归排序算法,用以上方法实现的话,算法的开销(时间复杂度和空间复杂度),以及实际效率会是如何,有实际意义么。问题描述不全,毕竟第一次在CSDN提问,望前辈们多看看。本人大二,学了c++ java。

3个回答

zhao4zhong1
zhao4zhong1   Rxr 2014.12.02 14:23
已采纳
caozhy
caozhy   Ds   Rxr 2014.12.01 23:05

完全可行,而且使用自己的栈或者递归,相同的算法的时间复杂度空间复杂度是没有变化的。

eagleyan
eagleyan   Rxr 2014.12.05 00:46

quicksort有in-place的实现,不需要额外的栈啊。至于mergesort,你也不需要栈,只需要一个可以copy的数组

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!