java - java中的合并排序实现是将一个值复制到另一个索引中而不是交换

Question

我正在实现一个合并排序算法。但是，出于某种原因，我的代码不断复制其中一个值并将其放回到我的数组中两次，而不是进行交换。我想知道是否有人可以看一下并让我知道这可能发生在哪里以及如何解决它。

public static void mergeSort(int[] a, int p, int r) {
    int q;
    if (p < r) {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

private static void merge(int[] a, int p, int q, int r) {
    int s1 = q - p + 1;
    int s2 = r - q;

    int B[] = new int[s1];
    int C[] = new int[s2];

    for (int i = 0; i < s1; i++) {
        B[i] = a[p + i];
    }
    for (int j = 0; j < s2; j++) {
        C[j] = a[q + 1 + j];
    }
    int i = 0;
    int j = 0;
    int k = p;
    while (i < s1 && j < s2) {
        if (B[i] <= C[j]) {
            a[k] = B[i];
            i++;
        } else {
            a[k] = C[j];
            j++;
        }
        k++;
    }

    while (i < s1) {
        a[k] = B[i];
        i++;
        k++;
    }
    while (j < s2) {
        a[k] = B[j];
        j++;
        k++;
    }
}

我当前对一个实例的输入是:{ 1317884528, 359761860, -513283737, 369485540, 564749187 }

输出为:{ -513283737, 359761860, 369485540, 369485540, 1317884528 }

我可以看出它的排序有些正确，但交换时遇到问题。

Answer 1

最后一个循环不正确:它应该从 C 复制剩余元素，而不是从 B:

while (j < s2) {
    a[k] = C[j];
    j++;
    k++;
}

请注意，如果 mergeSort 的 r 参数是第一个排除的索引而不是最后一个包含的索引，则代码会更简单并且不太容易出现一个错误:

/* sort an array of integers `a[]`. call as `mergeSort(a, 0, a.length)` */
public static void mergeSort(int[] a, int p, int r) {
    if (r - p > 1) {
        int q = p + (r - p + 1) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q, r);
        merge(a, p, q, r);
    }
}

private static void merge(int[] a, int p, int q, int r) {
    int s1 = q - p;
    int s2 = r - q;

    /* save the left part, the right part does not need saving */
    int B[] = new int[s1];
    for (int i = 0; i < s1; i++) {
        B[i] = a[p + i];
    }
    int i = 0;
    int j = q;
    int k = p;
    while (i < s1 && j < r) {
        if (B[i] <= a[j]) {
            a[k++] = B[i++];
        } else {
            a[k++] = a[j++];
        }
    }
    while (i < s1) {
        a[k++] = B[i++];
    }
}