相关疑难解决方法(0)

在不使用递归的情况下,对二叉树进行后序遍历的算法是什么？

尾递归是函数式语言中一个重要的性能优化策略,因为它允许递归调用消耗常量堆栈(而不是O(n)).

是否有任何问题根本无法以尾递归方式编写,或者总是可以将天真递归函数转换为尾递归函数？

如果是这样,有一天功能编译器和解释器可能足够智能以自动执行转换？

我在理解这种行为时遇到了一些麻烦.我正在使用timeit-module测量执行时间,并获得10000个周期的以下结果:

• 合并:1.22722930395
• 泡泡:0.810706578175
• 选择:0.469924766812

这是我的MergeSort代码:

def mergeSort(array):
    if len(array) <= 1:
        return array
    else:
        left = array[:len(array)/2]
        right = array[len(array)/2:]
        return merge(mergeSort(left),mergeSort(right))

def merge(array1,array2):
    merged_array=[]
    while len(array1) > 0 or len(array2) > 0:

        if array2 and not array1:
            merged_array.append(array2.pop(0))

        elif (array1 and not array2) or array1[0] < array2[0]:
            merged_array.append(array1.pop(0))

        else:
            merged_array.append(array2.pop(0))
    return merged_array

编辑:

我已经将列表操作更改为使用指针,我的测试现在可以使用0-1000的1000个随机数列表.(顺便说一句:我在这里改为10个周期)

结果:

• 合并:0.0574434420723
• 泡泡:1.74780097558
• 选择:0.362952293025

这是我重写的合并定义:

def merge(array1, array2):
    merged_array = []
    pointer1, pointer2 = 0, 0
    while pointer1 < len(array1) and …