eclipse简单合并排序Java

Question

我明天要交一个班级实验课，我完全被难倒了。要求很简单：制作一个mergeSort算法，使用可比较项对给定的ArrayList进行排序。“a”将有最终的排序列表。它目前正在抛出以下命令：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1
at java.util.ArrayList.rangeCheck(ArrayList.java:653)
at java.util.ArrayList.get(ArrayList.java:429)
at Sorts.merge(Sorts.java:142)
at Sorts.mergesort(Sorts.java:161)
at Sorts.mergesort(Sorts.java:160)
at Sorts.mergesort(Sorts.java:159)
at SortStep.sortMenu(SortStep.java:65)
at SortStep.main(SortStep.java:168)

什么都行！谢谢（我知道电话号码帮不了你们。对不起！）

/**
 * Takes in entire vector, but will merge the following sections together:
 * Left sublist from a[first]..a[mid], right sublist from a[mid+1]..a[last].
 * Precondition: each sublist is already in ascending order
 *
 * @param a
 *            reference to an array of integers to be sorted
 * @param first
 *            starting index of range of values to be sorted
 * @param mid
 *            midpoint index of range of values to be sorted
 * @param last
 *            last index of range of values to be sorted
 */
private void merge(ArrayList<Comparable> a, int first, int mid, int last) {
    ArrayList<Comparable> temp = new ArrayList<Comparable>();

    while (first <= mid && mid <= last) {
        if (a.get(first).compareTo(a.get(mid)) > 0) {
            temp.add(a.get(first));
            first++;
        } else {
            temp.add(a.get(mid));
            mid++;
        }
    }

    while (first < mid) {
        temp.add(a.get(first));
        first++;
    }

    while (mid <= last) {
        temp.add(a.get(mid));
        mid++;
    }

    for (int i = 0; i <= last; i++)
        a.set(i, temp.get(i));
}

/**
 * Recursive mergesort of an array of integers
 *
 * @param a
 *            reference to an array of integers to be sorted
 * @param first
 *            starting index of range of values to be sorted
 * @param last
 *            ending index of range of values to be sorted
 */
public void mergesort(ArrayList<Comparable> a, int first, int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergesort(a, first, mid);
        mergesort(a, mid + 1, last);
        merge(a, first, last, mid);
    }
}

Answer 1

• 方法merge期望参数为first, mid, last，但传递的是first, last, mid
• mid正在向前移动，因此额外的元素可能存储在temp中
• merge的最后一个循环是错误的，它应该从调用该方法时first中的内容开始，而不是从0开始
• 每个部分的范围都是错误的

更正代码：

private void merge(ArrayList<Comparable> a, int first, int mid, int last) {
    ArrayList<Comparable> temp = new ArrayList<Comparable>();
    mid++;

    int firstFirst = first;
    int firstEnd = mid;
    while (first < firstEnd && mid <= last) {
        if (a.get(first).compareTo(a.get(mid)) > 0) {
            temp.add(a.get(first));
            first++;
        } else {
            temp.add(a.get(mid));
            mid++;
        }
    }

    while (first < firstEnd) {
        temp.add(a.get(first));
        first++;
    }

    while (mid <= last) {
        temp.add(a.get(mid));
        mid++;
    }

    for (int i = firstFirst; i <= last; i++)
        a.set(i, temp.get(i - firstFirst));
}

public void mergesort(ArrayList<Comparable> a, int first, int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergesort(a, first, mid);
        mergesort(a, mid + 1, last);
        merge(a, first, mid, last);
    }
}