合并分裂除以4

Question

我正在为学校解决一个练习，我们需要实现一个正常的合并，最重要的是一个额外的方法，它除以四，而不是两个元素。

2-分裂是有效的，但我不能设法使四分裂的工作。如果有人能把我引向正确的方向，那就太好了。

到目前为止，我得到的是：

public static void mergeSortNew(int[] a, int left, int right) { ;

    if (left < right) {
        int middle1 = (left + right) / 4;
        int middle2 = middle1 + 1 + middle1;
        int middle3 = middle2 + 1 + middle1;
        mergeSortNew(a, left, middle1);
        mergeSortNew(a, middle1, middle2);
        mergeSortNew(a, middle2, middle3);
        mergeSortNew(a, middle3, right);

        merge(a, left, middle1, middle2);
        merge(a, middle2, middle2 + middle1, middle3);
        merge(a, middle3, middle3 + middle1, right);
    }
}

public static void merge(int [] a, int left, int middle, int right) {

    int n1 = middle - left + 1;
    int n2 = right - middle;
    int[] leftHalf = new int[n1 + 1];
    int[] rightHalf = new int[n2 + 1];
    leftHalf[n1] = Integer.MAX_VALUE;
    rightHalf[n2] = Integer.MAX_VALUE;

    for (int i = 0; i < n1; i++) {
        leftHalf[i] = a[left + i];
    }

    for (int j = 0; j < n2; j++) {
        rightHalf[j] = a[middle + j + 1];
    }

    int i = 0, j = 0;

    for (int k = left; k <= right; k++) {
        if (leftHalf[i] <= rightHalf[j]) {
            a[k] = leftHalf[i++];
        } else {
            a[k] = rightHalf[j++];
        }
    }
}

Answer 1

代码中存在多个问题：

• 删除原型行末尾的伪;，
• ，您的约定中包含了left和right索引值，这让人感到困惑。使用包含第一个索引和排除最后一个索引的约定要简单得多，正如递归调用中所隐含的那样。
• --用于merge调用的索引是不正确的:在添加偏移量而不是长度时，middle2 + middle1是没有意义的。用这个代替：

合并(a，左侧，middle1，middle2)；//合并切片0和1到片01合并(a，middle2，middle3，右)；//合并切片2和3，合并到片23 merge(a，左侧，middle2，右)；// merge slice 01和23

• ，在merge方法中，依赖于哨兵值。这是不正确的，这种做法从根本上讲是有缺陷的，应该加以禁止。如果右片包含与Integer.MAX_VALUE相等的值，则函数将从左片复制哨兵，并继续在左片结束后读取，从而导致异常。相反，您应该测试两个索引值，并在其中一个切片被完全复制后复制其余的值。

以下是修改后的版本：

// sort a portion of an array from `a[left]` included to `a[right]` excluded
public static void mergeSortNew(int[] a, int left, int right) {
    int length = right - left;
    if (length >= 2) {
        int middle1 = left + length / 4;
        int middle2 = left + length / 2;
        int middle3 = middle2 + length / 4;
        mergeSortNew(a, left, middle1);
        mergeSortNew(a, middle1, middle2);
        mergeSortNew(a, middle2, middle3);
        mergeSortNew(a, middle3, right);

        merge(a, left, middle1, middle2);  // merge slice 0 and 1 into slice 01
        merge(a, middle2, middle3, right); // merge slice 2 and 3 into slice 23
        merge(a, left, middle2, right);    // merge slice 01 and 23
    }
}

public static void merge(int[] a, int left, int middle, int right) {
    int n1 = middle - left;
    int n2 = right - middle;
    int[] leftHalf = new int[n1];
    int[] rightHalf = new int[n2];

    for (int i = 0; i < n1; i++) {
        leftHalf[i] = a[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightHalf[j] = a[middle + j];
    }

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (leftHalf[i] <= rightHalf[j]) {
            a[k++] = leftHalf[i++];
        } else {
            a[k++] = rightHalf[j++];
        }
    }
    while (i < n1) {
        a[k++] = leftHalf[i++];
    }
    while (j < n2) {
        a[k++] = rightHalf[j++];
    }
}

对数组进行排序。

mergeSortNew(array, 0, array.length);