查找归并排序树的高度

Question

我有一个合并排序算法的实现。如何计算树的高度？

到目前为止我可以得到递归调用的次数，但不能得到树的高度：

static int swaps=0;
static long comparisons=0;
static int recursionsdepth=0;

public static int[] sort(int[] array) {

    recursionsdepth++;
    if (array.length > 1) {

        int middle = (int)(array.length / 2);

        int[] left = new int[middle];
        for (int i = 0; i <= left.length - 1; i++) {
            left[i] = array[i];
        }

        int[] right = new int[array.length - middle];
        for (int i = middle; i <= array.length - 1; i++) {
            right[i - middle] = array[i];
        }

        left = sort(left);
        right = sort(right);

        return merge(left, right);
    }
    else
    {  
        recursionsdepth--;
        return array;
    }
}

对于 {1,5,7,9} 递归调用是 3（{1,5,7,9} 是 1，{1,5} 是 1，{7,9} 是 1），但是树的高度是 2 .

Answer 1

只要数组大小大于1，Merge Sort就会将数组重复分成两个（几乎）相等的部分。它不关心数组的初始状态，即它会这样做，即使数组已经排序。现在，对于任何给定的长度为 n 的数组，只有一种方法可以做到这一点。因此，归并排序树的高度对于 n 是恒定的。那就是高度将是 ceil(log n)，其中 base 是 2。你实际上不需要运行你的程序来找到它。

由于 OP 在实际运行排序代码时拼命计算高度，因此这里是：

将一个附加变量传递给存储当前节点深度的排序函数。并使用一个全局变量来存储到目前为止已经达到的最大深度。下面的代码是对问题中发布的代码的轻微修改：

static int swaps=0;
static long comparisons=0;
static int recursionsdepth=0;

public static int[] sort(int[] array, int depth) { // at first call depth = 0

    recursiondepth = Math.max(recursiondepth, depth);
    if (array.length > 1) {

        int middle = (int)(array.length / 2);

        int[] left = new int[middle];
        for (int i = 0; i <= left.length - 1; i++) {
            left[i] = array[i];
        }

        int[] right = new int[array.length - middle];
        for (int i = middle; i <= array.length - 1; i++) {
            right[i - middle] = array[i];
        }

        left = sort(left, depth+1);
        right = sort(right, depth+1);

        return merge(left, right);
    }
    else
    {  
        return array;
    }
}

查找归并排序树的高度

FInd the height of a mergesort-tree

java

recursion

mergesort