递归合并排序只对数组的一半进行排序

Question

我正在尝试实现一个递归归并排序算法来对一个简单的整数数组进行排序，但是我在数组的后半部分得到了奇怪的索引值。前半部分似乎排序很好，考虑到它是递归实现的，这令人困惑。随机整数数组在我的主要方法中初始化。

public class MergeSort {

public static int Rounds = 1;
public static void MergeSort(Comparable[] ToSort, Comparable[] temp, int first, int last) {
    if(first < last) {
        int mid = (first + last) / 2;

        //Test Block
        System.out.print("For Round " + Rounds + ":\n");
        System.out.print("first = " + first + "   mid = " + mid + "   last = " + last + "\n");
        Rounds++;
        System.out.print("Array in Round " + (Rounds - 1) + " = {");
        for(int i = 0; i <= ToSort.length - 1; i++) {
            System.out.print(ToSort[i]);
            if(i < ToSort.length - 1)
                System.out.print(", ");
            else {
                System.out.print("}\n\n");
            }
        }

        MergeSort(ToSort, temp, first, mid);
        MergeSort(ToSort, temp, mid + 1, last);
        Merge(ToSort, temp, first, mid + 1, last);
    }

}

public static void Merge(Comparable[] ToSort, Comparable[] temp, int first, int mid, int last) {
    int beginHalf1 = first;
    int endHalf1 = mid - 1;
    int beginHalf2 = mid;
    int endHalf2 = last;
    int index = first;
    int Elements = (last - first) + 1;

    while(beginHalf1 <= endHalf1 && beginHalf2 <= endHalf2) {
        if(ToSort[beginHalf1].compareTo(ToSort[beginHalf2]) < 0) temp[index++] = ToSort[beginHalf1++];
        else temp[index++] = ToSort[beginHalf2++];
    }

    while(beginHalf1 <= endHalf1) temp[index++] = ToSort[beginHalf1++];
    while(beginHalf2 <= endHalf2) temp[index++] = ToSort[beginHalf2++];
    for(int i = 0; i < Elements; i++, last--) ToSort[last] = temp[last];

}

}

这会产生以下输出：

未排序数组 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87} 对于第 1 轮：第一个 = 0 中间 = 4 最后一个 = 9 第 1 轮中的数组 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87}

第 2 轮：第一个 = 0 中间 = 2 最后一个 = 4 第 2 轮中的数组 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87}

第 3 轮：第一个 = 0 中间 = 1 最后一个 = 2 第 3 轮中的数组 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87}

第 4 轮：第一个 = 0 中间 = 0 最后一个 = 1 第 4 轮中的数组 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87}

第 5 轮：第一个 = 3 中间 = 3 最后一个 = 4 第 5 轮中的数组 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

第 6 轮：第一个 = 5 中间 = 7 最后一个 = 9 第 6 轮中的数组 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

第 7 轮：第一个 = 5 中间 = 6 最后一个 = 7 第 7 轮中的数组 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

第 8 轮：第一个 = 5 中间 = 5 最后一个 = 6 第 8 轮中的数组 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

第 9 轮：第一个 = 8 中间 = 8 最后一个 = 9 第 9 轮中的数组 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

Answer 1

你的实现没有错误。如果在应用 MergeSort 方法后打印数组，则它被排序：

Comparable[] a = new Comparable[]{15, 9, 12, 19, 49, 43, 57, 70, 78, 87};
Comparable[] b = new Comparable[a.length];
MergeSort.MergeSort(a, b, 0, a.length - 1);

for (int i = 0; i <= a.length - 1; i++) {
    System.out.print(a[i]);
    if (i < a.length - 1)
        System.out.print(", ");
    else {
        System.out.print("}\n\n");
    }
}

将打印 9, 12, 15, 19, 43, 49, 57, 70, 78, 87}

递归合并排序只对数组的一半进行排序

Recursive mergesort only sorts half of an array

java

recursion

mergesort