Nik*_*nka 3 language-agnostic sorting algorithm merge mergesort
我一直在阅读塞奇威克和韦恩的"算法,第四版".本书介绍了两种使用合并排序的方法.使用标准的自顶向下递归合并排序或自底向上合并排序.
是否存在自下而上合并排序比自上而下版本更受欢迎的情况？
Meh*_*dad 8
递归mergesort需要O(log n)空间用于递归堆栈,但自下而上的版本可以让你做得更好(没有递归堆栈,只有几个整数跟踪你在输入中的位置).
O(log n)
如果您遇到一些不支持递归的语言,并且只为堆栈(可能是嵌入式系统？)提供有限的内存,那么自下而上的版本将是您唯一的选择.
这是一个自下而上的版本,显示了我的意思.
归档时间：
12 年，8 月 前
查看次数：
3458 次
最近记录：
11 年，11 月 前