mergesort / merge-method的实现

Question

我试图实现mergesort算法。合并方法可能是错误的。到目前为止，这是我的代码：

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    mergesort(list, 0, list.size() - 1);
}   

private static <T extends Comparable<? super T>> void mergesort(List<T> list, int i, int j) {
    if (j - i < 1)
        return;
    int mid = (i + j) / 2;
    mergesort(list, i, mid);
    mergesort(list, mid + 1, j);
    merge(list, i, mid, j);
}

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int half = q - p + 1;
    int otherhalf = r - q;

    List<T> left = new ArrayList<T>();
    List<T> right = new ArrayList<T>();

    for (int i = 0; i < half; i++) {
        left.add(i, a.get(p + i));
    }
    for (int i = 0; i < otherhalf; i++) {
        right.add(i, a.get(q + i + 1));
    }

    int leftindex, rightindex, resultindex;
    leftindex = rightindex = resultindex = 0;

    while (leftindex < left.size() || rightindex < right.size()) {

        if (leftindex < left.size() && rightindex < right.size()) {

            if (left.get(leftindex).compareTo(right.get(rightindex)) < 0) {
                a.set(resultindex, left.get(leftindex));
                resultindex++;
                leftindex++;
            } else {
                a.set(resultindex, right.get(rightindex));
                resultindex++;
                rightindex++;
            }
        } else if (leftindex < left.size()) {
            a.set(resultindex, left.get(leftindex));
            resultindex++;
            leftindex++;
        } else if (rightindex < right.size()) {
            a.set(resultindex, right.get(rightindex));
            resultindex++;
            rightindex++;
        }   
    }
}

我测试了它。作为输入，我选择[5, 6, 1, 4]。

输出是：[1, 1, 4, 4]：

似乎我没有在合并方法中到达位置5和6。所以我想，我必须增加一些东西，但我不知道在哪里？有谁能够帮我 ？

Answer 1

问题是resultindex初始化为0而不是p。

以下是一些其他说明：

• 使用右边界的第一个排除值的索引而不是最后一个元素的索引会更简单。它避免了可能由一个错误引起的+ 1调整。
• 比较应该是if (left.get(leftindex).compareTo(right.get(rightindex)) <= 0)而不是<，以确保稳定的排序。
• 测试else if (rightindex < right.size())是多余的。
• 你可以通过编写3个循环减少测试次数：只要两个半部分都有成员就可以减少一个，然后一个复制剩下的左半部分，最后一个复制剩下的右半部分。
• 你的变量名在java中不是惯用的。

这是一个更正版本：

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    mergesort(list, 0, list.size());
}   

private static <T extends Comparable<? super T>> void mergesort(List<T> list, int i, int j) {
    if (j - i < 2)
        return;
    int mid = (i + j) / 2;
    mergesort(list, i, mid);
    mergesort(list, mid, j);
    merge(list, i, mid, j);
}

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int leftLen = q - p;
    int rightLen = r - q;

    List<T> left = new ArrayList<T>();
    List<T> right = new ArrayList<T>();

    for (int i = 0; i < leftLen; i++) {
        left.add(i, a.get(p + i));
    }
    for (int i = 0; i < rightLen; i++) {
        right.add(i, a.get(q + i));
    }

    int leftIndex = 0;
    int rightIndex = 0;
    int resultIndex = p;

    while (leftIndex < leftLen && rightIndex < rightLen) {
        if (left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0) {
            a.set(resultIndex, left.get(leftIndex));
            resultIndex++;
            leftIndex++;
        } else {
            a.set(resultIndex, right.get(rightIndex));
            resultIndex++;
            rightIndex++;
        }
    }
    while (leftIndex < leftLen) {
        a.set(resultIndex, left.get(leftIndex));
        resultIndex++;
        leftIndex++;
    }
    while (rightIndex < rightLen) {
        a.set(resultIndex, right.get(rightIndex));
        resultIndex++;
        rightIndex++;
    }   
}

此外，没有必要保存右半部分，因为它的元素在复制之前永远不会被覆盖。确实复制右半部分的其余部分是没用的，因为这些元素已经到位。

这是一个简化版本：

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int half = q - p;
    List<T> left = new ArrayList<T>();

    for (int i = 0; i < half; i++) {
        left.add(i, a.get(p + i));
    }

    int leftIndex = 0;
    int rightIndex = q;
    int resultIndex = p;

    while (leftIndex < half && rightIndex < r) {
        if (left.get(leftIndex).compareTo(a.get(rightIndex)) <= 0) {
            a.set(resultIndex, left.get(leftIndex));
            resultIndex++;
            leftIndex++;
        } else {
            a.set(resultIndex, a.get(rightIndex));
            resultIndex++;
            rightIndex++;
        }
    }
    while (leftIndex < half) {
        a.set(resultIndex, left.get(leftIndex));
        resultIndex++;
        leftIndex++;
    }
}

进一步简化代码：

• List数组不需要动态left，
• 一些局部变量也可以省略
• 组合测试使最后一个循环无用。

这是简化但可能不太可读的代码：

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int i, half = q - p;
    T[] left = new T[half];

    for (i = 0; i < half; i++)
        left[i] = a.get(p + i);

    for (i = 0; i < half; ) {
        if (q == r || left[i].compareTo(a.get(q)) <= 0)
            a.set(p++, left[i++]);
        else
            a.set(p++, a.get(q++));
    }
}