u011456891
我和科比都惊呆了
2014-12-01 14:07
采纳率: 50%
浏览 2.0k
已采纳

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • zhao4zhong1
    赵4老师 2014-12-02 06:23
    已采纳
    点赞 评论
  • caozhy

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

    点赞 评论
  • eagleyan
    Coursera 2014-12-04 16:46

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

    点赞 评论

相关推荐