java - 我合并两个已排序数组有什么问题吗？

Question

void sort(int a[], int b[], int m, int n)
    {
        int e = m + n;
        while(m >=0 && n >=0)
        {
            if(a[m] > b[n])
            {
                a[e] = a[m];
                m--;
                e--;
            }
            else if(a[e] < b[n])
            {
                a[e] = b[n];
                n--;
                e--;
            }
            else
            {
                a[e] = b[n];
                e--;
                n--;
                m--;
            }
        }
    }

public static void main(String[] args) {
        SortSorted obj = new SortSorted();
        int a[] = new int [6];
        int b[] = new int [3];
        a[0] = 1;
        a[1] = 2;
        a[2] = 3;
        b[0] = 2;
        b[1] = 7;
        b[2] = 8;
        obj.sort(a,b, 2, 2);
    }

在添加和不添加第三个 else 条件的情况下，我得到的输出为 1 2 3 7 8 0 而不是 1 2 2 3 7 8。

Answer 1

您的 e 起始值太低，应该是 m + n + 1。

想一想，对于两个三元素数组，m 和 n 都是两个。这意味着您将从 m + n 4 开始，而对于 6 元素结果，您应该从 5 开始。

这是一个相对简单的相差一错误。

您还可以通过简单地忽略相等性来解决当值相等时丢失值的其他问题。如果大于或等于，则选择 a，否则选择 b。

并且您的循环继续逻辑是错误的，如果您首先耗尽 a (使用 a = {2, 2, 3} 和 b = {1, 7, 8} 看看我的意思)。仅当 a 和 b 都剩余元素时才可以继续。当其中任何一个还有剩余元素时，您应该继续。

您可以通过按原样保留该循环但添加其他两个循环(其中只有一个实际上会执行任何操作)来耗尽另一个列表来解决此问题。

作为支持，我提供了以下 C 代码(因为我的速度比 Java 更快，但排序例程本身应该几乎相同):

#include <stdio.h>

void sort (int a[], int b[], int m, int n) {
    // Start at correct offset for target array.

    int e = m + n + 1;

    // Until one list empty, choose the correct value.

    while (m >= 0 && n >= 0)
        if (a[m] >= b[n])
            a[e--] = a[m--];
        else
            a[e--] = b[n--];

    // If b was empty, just transfer a.

    while (m >= 0)
        a[e--] = a[m--];

    // If a was empty, just transfer b.

    while (n >= 0)
        a[e--] = b[n--];
}

还有一些测试代码:

int main(void) {
    int a[6] = {2,2,3};
    int b[] = {1,7,8};
    sort (a, b, 2, 2);
    printf ("%d %d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4], a[5]);
    return 0;
}

其输出是:

1 2 2 3 7 8

正如预期的那样。

<小时/>

以及等效的 Java 代码:

class Test {
    static void sort (int a[], int b[], int m, int n) {
        // Start at correct offset for target array.

        int e = m + n + 1;

        // Until one list empty, choose the correct value.

        while (m >= 0 && n >= 0)
            if (a[m] >= b[n])
                a[e--] = a[m--];
            else
                a[e--] = b[n--];

        // If b was empty, just transfer a.

        while (m >= 0)
            a[e--] = a[m--];

        // If a was empty, just transfer b.

        while (n >= 0)
            a[e--] = b[n--];
    }

及其测试套件:

    static public void main(String[] args) {
        int a[] = new int[6];
        a[0] = 2; a[1] = 2; a[2] = 3;
        int b[] = new int[3];
        b[0] = 1; b[1] = 7; b[2] = 8;
        sort (a, b, 2, 2);
        for (int i = 0; i < 6; i++)
            System.out.println (a[i]);
    }
}  

<小时/>

事实上，由于您无论如何都要写入 a，因此您实际上可以省略中间循环(while (m >= 0) 循环)。那是因为，在这种情况下，您只是将元素转移给它们自己。

我将保留它，因为如果您要写入的数组不在就位，它就变得很重要，但如果您希望针对特定情况，可以将其删除。