Java 中合并两个有序数组

简介

在 Java 编程中，合并两个有序数组是一个常见的任务。有序数组是指数组中的元素按照升序或降序排列。合并两个有序数组意味着将这两个数组合并成一个新的有序数组。这个操作在许多算法和数据处理场景中都非常有用，比如在排序算法的归并步骤，以及数据整合操作中。

目录

1. 基础概念
2. 使用方法
   • 简单合并方法
   • 优化合并方法
3. 常见实践
   • 在排序算法中的应用
   • 数据处理中的应用
4. 最佳实践
   • 性能优化
   • 代码可读性优化
5. 小结
6. 参考资料

基础概念

合并两个有序数组的核心思想是遍历这两个数组，比较它们的元素，并按照顺序将元素放入一个新的数组中。由于数组已经是有序的，我们可以利用这个特性，通过一次遍历就完成合并操作。

假设有两个有序数组 arr1 和 arr2，我们需要创建一个新的数组 result 来存储合并后的结果。我们使用两个指针，分别指向 arr1 和 arr2 的起始位置，然后比较指针指向的元素，将较小的元素放入 result 数组中，并将相应的指针后移一位。重复这个过程，直到其中一个数组遍历完，然后将另一个数组中剩余的元素直接复制到 result 数组的末尾。

使用方法

简单合并方法

下面是一个简单的 Java 代码示例，展示如何合并两个有序数组：

public class MergeSortedArrays {
    public static int[] mergeArrays(int[] arr1, int[] arr2) {
        int n1 = arr1.length;
        int n2 = arr2.length;
        int[] result = new int[n1 + n2];
        int i = 0, j = 0, k = 0;

        while (i < n1 && j < n2) {
            if (arr1[i] <= arr2[j]) {
                result[k] = arr1[i];
                i++;
            } else {
                result[k] = arr2[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            result[k] = arr1[i];
            i++;
            k++;
        }

        while (j < n2) {
            result[k] = arr2[j];
            j++;
            k++;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5};
        int[] arr2 = {2, 4, 6};
        int[] mergedArray = mergeArrays(arr1, arr2);

        for (int num : mergedArray) {
            System.out.print(num + " ");
        }
    }
}

优化合并方法

上述方法虽然有效，但在空间复杂度上不够优化，因为我们创建了一个新的数组来存储结果。可以通过在原数组上进行操作来优化空间复杂度。

public class MergeSortedArraysOptimized {
    public static void mergeInPlace(int[] arr1, int[] arr2) {
        int n1 = arr1.length;
        int n2 = arr2.length;
        int[] temp = new int[n1];

        for (int i = 0; i < n1; i++) {
            temp[i] = arr1[i];
        }

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

        while (i < n1 && j < n2) {
            if (temp[i] <= arr2[j]) {
                arr1[k] = temp[i];
                i++;
            } else {
                arr1[k] = arr2[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr1[k] = temp[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr1[k] = arr2[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5};
        int[] arr2 = {2, 4, 6};

        mergeInPlace(arr1, arr2);

        for (int num : arr1) {
            System.out.print(num + " ");
        }
    }
}

常见实践

在排序算法中的应用

合并两个有序数组是归并排序算法中的关键步骤。归并排序是一种分治算法，它将一个数组分成两个子数组，分别对它们进行排序，然后将两个有序的子数组合并成一个有序的数组。

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        for (int i = 0; i < mid; i++) {
            left[i] = arr[i];
        }

        for (int i = mid; i < arr.length; i++) {
            right[i - mid] = arr[i];
        }

        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int n1 = left.length;
        int n2 = right.length;
        int i = 0, j = 0, k = 0;

        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
        mergeSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

数据处理中的应用

在数据处理场景中，我们可能需要将两个有序的数据集合并成一个有序的数据集。例如，在数据库查询结果的合并或者日志文件的合并中。

import java.util.ArrayList;
import java.util.List;

public class DataMerge {
    public static List<Integer> mergeData(List<Integer> data1, List<Integer> data2) {
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;

        while (i < data1.size() && j < data2.size()) {
            if (data1.get(i) <= data2.get(j)) {
                result.add(data1.get(i));
                i++;
            } else {
                result.add(data2.get(j));
                j++;
            }
        }

        while (i < data1.size()) {
            result.add(data1.get(i));
            i++;
        }

        while (j < data2.size()) {
            result.add(data2.get(j));
            j++;
        }

        return result;
    }

    public static void main(String[] args) {
        List<Integer> data1 = new ArrayList<>();
        data1.add(1);
        data1.add(3);
        data1.add(5);

        List<Integer> data2 = new ArrayList<>();
        data2.add(2);
        data2.add(4);
        data2.add(6);

        List<Integer> mergedData = mergeData(data1, data2);
        System.out.println(mergedData);
    }
}

最佳实践

性能优化

• 减少不必要的内存分配：如上述优化合并方法所示，尽量在原数组上进行操作，避免创建过多的临时数组。
• 使用更高效的数据结构：在某些情况下，使用链表结构可能比数组更适合合并操作，因为链表的插入操作时间复杂度更低。

代码可读性优化

• 提取方法：将合并逻辑提取到独立的方法中，使代码结构更清晰，便于维护和复用。
• 添加注释：在关键的代码段添加注释，解释代码的功能和意图，提高代码的可读性。

小结

合并两个有序数组是 Java 编程中的一个重要操作，它在排序算法、数据处理等多个领域都有广泛应用。通过理解基本概念和掌握不同的实现方法，以及遵循最佳实践原则，我们可以写出高效、可读的代码来完成这一任务。

参考资料

• 《Effective Java》
• Oracle Java 官方文档
• LeetCode 相关题目及讨论区