时间戳

首页 > 解决方案 > 合并排序/合并方法的实现

java - 合并排序/合并方法的实现

问题描述

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

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。所以我想，我必须增加一些东西，但我不知道在哪里？有谁能够帮我 ？

标签： javasortingmergemergesort

解决方案

问题被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++));
    }
}

推荐阅读