合并拆分除以 4

Question

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

2-split 工作正常，但我无法使 4-split 工作。如果有人能引导我走向正确的方向，那就太好了。

这是我目前得到的：

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

您可以使用

对数组进行排序

mergeSortNew(array, 0, array.length);

合并拆分除以 4

merge split divide by 4

java

mergesort