合并拆分除以4

Question

我正在为学校解决一项练习，我们需要实现一个普通的mergesort，最重要的是，该方法确实将其除以四个而不是两个元素。

2分割正在工作，但我无法设法使4分割工作。如果有人可以引导我朝正确的方向发展，那就太好了。

这是我到目前为止所得到的：

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没有意义，因为您要添加偏移量而不是长度。改用它：

  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
  

• 在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++];
    }
}