java - 如何正确合并两个已排序的数组？

Question

合并两个排序数组的正确方法是什么？我目前正在开发一个简短的 Java 程序来合并两个已经排序的数组。请在下面找到我的代码。

public class Merge {

    // data
    private static int[] data;
    private int elements;

    // constructor
    public Merge()
    {
        data = new int[4];
        elements = 0;
    }

    // DoubleSize method doubles array size if needed
    public void DoubleSize()
    {
        int[] tmp = new int[2 * data.length];
        // transfer existing data
        for (int i = 0; i < elements; i++)
        {
            tmp[i]=data[i]; 
        }
        data = tmp;
    }

    // this methods adds to the end of an array 
    public void add(int val)    
    {
        if(elements >= data.length)
        {
            DoubleSize();
        }
        data[elements] = val;
        elements++;
    }

    // this method prints the array values
    public void print()
    {
        // for-loop to print valid data only
        for(int i = 0; i < elements; i++)
        {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }
    // this method gets a value given an index
    public int get(int loc)
    {
        return data[loc];
    }

    // set a value, given an index
    public void set(int loc, int value)
    {
        data[loc]= value;
    }

    // this method sorts the data in array in ascending order
    public void sort()
    {
        int[] tmp2 = new int[data.length];
        for(int i = 0;i < data.length; i++)
        {
            int loc = this.min();
            tmp2[i] = this.get(loc);
            data[loc] = this.get(this.max())+1;
        }
        data = tmp2;
    }

    public int[] merge(int[] data2)
    {
        int[] data3 = new int[data.length + data2.length];
        int i = 0, j = 0, k = 0; 

        // Traverse both array 
        while (i < data.length && j < data2.length) 
        { 
            // Check if current element of first 
            // array is smaller than current element 
            // of second array. If yes, store first 
            // array element and increment first array 
            // index. Otherwise do same with second array 
            if(data[i] < data2[j]) { 
                data3[k] = data[i]; 
                i++;
            }
            else {
                data3[k] = data2[j]; 
                j++;
            }

        } 

        // Store remaining elements of first array 
        while (i < data.length) {
            data3[k] = data[i]; 
            i++;
            k++;
        }

        // Store remaining elements of second array 
        while (j < data2.length) {
            data3[k] = data2[j];
            j++;
            k++;
        }
        return data3;
    }

    // main method to test our previous methods
    public static void main(String[] args)
    {
        Merge array = new Merge();

        // adding in numbers to sort 
        array.add(-7);
        array.add(2);
        array.add(4);
        array.add(9);
        array.add(13);
        array.print();  
        array.merge(new int[] {-9, 1, 6, 22});
        array.print();

    }
}

当前输出只是:

The following elements have been added to the array:

-7 2 4 9 13 

-7 2 4 9 13

我似乎无法弄清楚为什么这没有按预期工作。任何帮助将不胜感激!

Answer 1

您的代码中有很多错误。

我将一一解决它们，同时只解释它们，而不提供实际的完整解决方案 - 因为我怀疑您正在解决家庭作业问题。

public void DoubleSize()

功能问题(阻止您的代码正确运行)

• 您的代码无法编译。 public void sort() 中的 this.min() 和 this.max() 未定义。

• 您的方法 public int[] merge(int[] data2) 返回合并的数组。然而你从来没有对这个数组做任何事情。让该方法不返回任何内容，而是将新创建的数组设置为类的成员 (data)。

• 您没有在 merge 的第一个循环中递增变量 k。它始终为 0，这意味着您始终写入数组中的同一位置。

• 合并后不更新变量elements

• 在 merge 的主循环中，您将迭代 i 直到 data.length。考虑到这包括数组的末尾，其中填充有 0。也许您想使用另一个变量？

• 在merge中的主循环之后，您将从data复制所有剩余元素，但正如我们刚才所说，它们都是0。所以完全跳过这一部分

实现上述所有内容将产生一个有效的解决方案。我自己测试过

其他问题(不是故障原因，但仍然很重要)

• Java 命名约定规定方法名称应使用小写首字母拼写。这称为“camelCase”(您使用了“CamelCase”)。这不是您的代码无法运行的原因，但这是一个很好的做法。

• 您的成员data 被声明为静态。静态成员属于类，而不属于对象。您应该使该成员成为非静态的!

• 您并不严格需要变量 k，因为 k == (i + j) 应始终为 true 。简化这一点将消除第一个列表中的一个问题!