有没有更好的方法将两个已排序数组合并成另一个已排序数组？

Question

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arrA = {2,3,4};
        int[] arrB = {5,6,7,8};
        mergeArray(arrA,arrB);
    }
    static void mergeArray(int[] arrA,int[] arrB){

        int len = arrA.length+arrB.length;
        int lenA = arrA.length;
        int lenB = arrB.length;
        int a=0,b=0,c=0;
        int temp=0;
        int[] arrC = new int[len];
        for(int i=0; i < lenA; i++){
            arrC[i] = arrA[i];
        }
        for(int j=lenA,k=0; (k < lenB) && (j < len) ; j++,k++){
            arrC[j] = arrB[k];
        }
        for(int n=0; n < len ; n++){
            for(int m=0; m < len; m++ ){
                if(arrC[n] < arrC[m]){
                    temp  = arrC[n];
                    arrC[n] = arrC[m];
                    arrC[m] = temp;
                }
            }
        }
        for(int x : arrC){
            System.out.println(x);
        }
    }

结果: {2,3,4,5,6,7,8}

我正在尝试将这些值放入一个新的数组中并再次排序。有没有人能给我比这更好的解决方案。

- user1918566

---

这个有什么问题吗？ - beaker

我想要比这个更好的解决方案。@beaker - user1918566

请查看System#arrayCopy。 - JonK

由于这两个数组已经排序，您可以将较小的元素复制到新数组中，重复此过程直到一个输入数组用尽，然后复制另一个数组的剩余部分。 - Henry

有很多解决方案可以不使用库方法来完成，但是为什么要避免它们呢？它们就是用来被使用的。 - JonK

Answer 1

您可以使用Java8流：

    int[] arrA = {2,3,4};
    int[] arrB = {5,6,7,8};
    int[] mergedArray = IntStream.concat(Arrays.stream(arrA), Arrays.stream(arrB)).toArray();

如果顺序很重要：

IntStream.concat(Arrays.stream(arrA), Arrays.stream(arrB)).sorted().toArray();

在这种情况下，你不仅可以将其转换为数组，还可以转换为任何你想要的东西。

- dvelopp

Answer 2

我回忆起了过去的学校时光！这里提供解决方案！没有库，只有简单的代码！享受吧。

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int [] array1 = {5, 1, 4, 5, 7, 8, 1, 0, 4};
        int [] array2 = {4, 7, 1, 0, 9, 3};

        System.out.println("Array 1");
        print(array1);

        System.out.println("Array 2");
        print(array2);

        Arrays.sort(array1);
        Arrays.sort(array2);

        System.out.println("Sorted array 1");
        print(array1);

        System.out.println("Sorted array 2");
        print(array2);

        int [] mergedAndSortedArray = mergeSorted(array1, array2);

        System.out.println("Sorted merged array");
        print(mergedAndSortedArray);
    }

    private static void print(int [] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }

        System.out.println("\n");
    }

    private static int [] mergeSorted(int [] array1, int [] array2) {
        int [] res = new int [array1.length + array2.length];

        int i = 0;
        int j = 0;
        int k = 0;

        //Do your homework. First loop until you reach end of either array, and then add the rest elements.

        return res;
    }
}

这是结果

Array 1
5 1 4 5 7 8 1 0 4 

Array 2
4 7 1 0 9 3 

Sorted array 1
0 1 1 4 4 5 5 7 8 

Sorted array 2
0 1 3 4 7 9 

Sorted merged array
0 0 1 1 1 3 4 4 4 5 5 7 7 8 9 

更新

如果您需要将 N 个已排序的数组合并成一个已排序的数组，您可以通过递归地一对一对地合并它们（合并第一个和第二个数组，第三个和第四个数组等），然后再次执行此操作，直到您有两个数组，并最终将它们合并！

- Yan Khonski

---

请参阅如何提问和回答作业问题。"如果您认为完整的代码示例对学生没有帮助，那么最好不要提供它，要根据自己的判断力。" - Andy Thomas

此外，不鼓励使用“+1”评论。 - Andy Thomas

你创建了一个新的回答，而不是编辑这个回答。 - Andy Thomas

只為每位用戶提供一個適當的答案即可。 - Andy Thomas

@AndyThomas 好的，我已经删除了第二个答案。我删除了作业解决方案，只是用语言解释了这个想法。说到作业，其他一些答案可以复制粘贴。 - Yan Khonski

Answer 3

简单来说，你正在将一个数组连接到另一个数组，然后进行冒泡排序。冒泡排序的最差情况时间复杂度为O(n^2)。这意味着排序所需的时间可能随着两个输入数组长度之和的平方而增加。

但是你已经知道这两个数组是有序的。在写入合并后的数组时，你只需要查看两个输入数组的头部即可。下一次写入将是两者中的最小值。你的合并时间复杂度为O(n)，其中n是两个输入数组长度之和。

这是归并排序算法的一部分。通常，归并排序在单个数组中就地排序。你的排序略有不同，使用两个排序好的数组，但思路是相同的。

- Andy Thomas

Answer 4

试试这个：

Integer[] mergeArray = (Integer[])ArrayUtils.addAll(arrA, arrB);

请看这个：

public static T[] addAll(T[] array1, T... array2)

然后：

Arrays.sort(mergeArray, Collections.reverseOrder());

- Carlos Laspina

---

我认为OP想要一个高效的归并排序，使得[1,3,5]和[2,4,6]合并成[1,2,3,4,5,6]。 - slim

为什么要将整数值转换为字符串？ - JonK

Answer 5

我想你是在寻求一种将两个已排序数组“压缩”在一起以得到一个排序数组的方法。我认为你已经意识到连接然后排序是低效的，因为它没有利用输入数组已经排序的优势。

我还假设这是一个作业或学习问题，所以我会高屋建瓴地描述解决方案。

您需要几个变量来跟踪您的位置：

- leftIndex（您在左侧输入中的位置） - rightIndex（您在右侧输入中的位置） - destinationIndex（您在目标中的位置）

从零开始所有索引。现在我们要选择一个数组进行操作，并逐个获取其中的值。

只要这些值小于另一个输入数组的下一个值，我们就将其添加到输出中。然后我们切换到另一个数组。我们不断地切换直到达到两个输入的末尾。

伪代码：

while (leftIndex and rightIndex are both within the length of their arrays) {
    while(leftInput[leftIndex] is less than rightInput[rightIndex]) {
         copy leftInput[leftIndex] into destination[destinationIndex]
         increment leftIndex
         increment destinationIndex
    }
    while(rightInput[rightIndex] is less than leftInput[leftIndex]) {
         copy rightInput[leftIndex] into destination[destinationIndex]
         increment rightIndex
         increment destinationIndex
    }
}

如果您直接将我所写的内容翻译成Java，可能会出现“ArrayIndexOutOfBounds”异常。您需要在“while”语句中添加额外的代码，以使其在数组的一个索引超过其末尾时执行正确操作。

- slim