【面试干货】 两个有序数组的合并排序

1、实现思想

使用两个指针分别指向两个数组的起始位置，然后逐个比较两个指针所指向的元素，将较小的元素依次放入新的数组中，同时移动相应的指针。

2、代码实现

package csdn; 

import java.util.Arrays; // 导入Arrays类，用于数组操作

public class Sort { // 定义名为Sort的类

    public static void main(String[] args) { // 主函数入口
        // 定义两个已排序的数组
        int[] num1 = new int[]{1, 4, 9, 67, 87, 955, 1564, 12354}; 
        int[] num2 = new int[]{-1, 0, 67, 113, 767, 879, 980};

        // 初始化两个指针a和b，分别指向数组num1和num2的起始位置
        int a = 0; 
        int b = 0; 
        // 定义一个新的数组，长度为两个原数组长度之和
        int[] num3 = new int[num1.length + num2.length]; 

        // 遍历新数组
        for (int i = 0; i < num3.length; i++) { 
            // 如果两个数组都还有元素未遍历完
            if (a < num1.length && b < num2.length) { 
                // 比较当前num1和num2的元素，将较小的加入num3，并移动对应指针
                if (num1[a] < num2[b]) { 
                    num3[i] = num1[a]; 
                    a++; // 移动num1指针
                } else {
                    num3[i] = num2[b]; 
                    b++; // 移动num2指针
                }
            } else if (a < num1.length) { // 如果num2已遍历完，但num1还有元素未加入num3
                num3[i] = num1[a]; // 将剩余的num1元素加入num3
                a++; // 移动num1指针
            } else if (b < num2.length) { // 如果num1已遍历完，但num2还有元素未加入num3
                num3[i] = num2[b]; // 将剩余的num2元素加入num3
                b++; // 移动num2指针
            }
        }

        // 打印排序后的数组num3
        System.out.println("排序后:" + Arrays.toString(num3)); 
    }
}

1. 初始化两个指针a和b，分别指向两个已排序数组num1和num2的起始位置。
2. 创建一个新的数组num3，用于存放合并后的结果，其长度为num1和num2长度之和。
3. 遍历新数组num3，循环条件为i从0到num3的长度减1。
4. 在循环中，首先判断两个指针a和b是否都没有越界（即是否都小于各自数组的长度）：
   • 如果都没有越界，则比较num1[a]和num2[b]的大小：
     • 如果num1[a]小于num2[b]，则将num1[a]放入num3中，并将指针a向后移动一位；
     • 如果num1[a]大于等于num2[b]，则将num2[b]放入num3中，并将指针b向后移动一位。
   • 如果有一个指针越界了（即数组已遍历完），则将另一个数组剩余部分直接放入num3中，不再进行比较。
5. 最后，输出排序后的数组num3。

这种合并已排序数组的方法称为"归并"（Merge）算法，时间复杂度为O(n)，其中n为两个数组的总长度。