关于java:美团一面两个有序的数组如何高效合并成一个有序数组

在说这个题目之前先来说说一个排序算法 “归并算法”

归并算法采取思维是分治思维，分治思维简略说就是分而治之，将一个大问题合成为小问题，将小问题解答后合并为大问题的答案。

乍一看跟递归思维很像，的确如此，分治思维个别就是应用递归来实现的。然而须要留神的是：递归是代码实现的形式，分治属于实践。

接下来看一副图了解下：

说完它的思维：咱们再来剖析下工夫复杂度。归并算法采纳的是齐全二叉树的模式。所以能够由齐全二叉树的深度能够得悉，整个归并排序须要进行log2n次。

而后每一次须要耗费O{n}工夫。所以总的工夫复杂度为o{nlog2n}。归并排序是一种比拟占用内存，然而效率高且稳固的算法

贴上代码：

static void Main(string[] args) {
    int[] arr = new int[] { 14,12,15,13,11,16 ,10};

    int[] newArr = Sort(arr, new int[7], 0, arr.Length - 1);
    for (int i = 0; i < newArr.Length - 1; i++)
    {
        Console.WriteLine(newArr[i]);
    }

    Console.ReadKey();
}

public static int[] Sort(int[] arr, int[] result, int start, int end)
{
    if (start >= end)
        return null;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    Sort(arr, result, start1, end1);
    Sort(arr, result, start2, end2);
    int k = start;
    //进行比拟。留神这里++是后执行的，先取出来数组中的值而后++
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    //将每个分组残余的进行复制
    while (start1 <= end1) 
        result[k++] = arr[start1++];
    //将每个分组残余的进行复制
    while (start2 <= end2)
        result[k++] = arr[start2++]; 
    for (k = start; k <= end; k++)
        arr[k] = result[k];
    return result;
}

说完了归并算法回到题目上来 首先剖析下 题目给定的是两个曾经排好序的数组合并，关键字“合并”，“两个”，正好合乎咱们的归并算法，并且曾经分类好了，只须要去合并就能够了。

来看下几张图。

蓝色的箭头示意最终抉择的地位，而红色的箭头示意两个数组以后要比拟的元素，比方以后是2与1比拟，1比2小，所以1放到蓝色的箭头中，蓝色的箭头后移，1的箭头后移。

而后2与4比拟，2比4小那么2到蓝色的箭头中，蓝色箭头后移，2后移，持续比拟…….

归并思路就是这样了，最初惟一须要留神的是那个先比拟完的话，那么剩下的间接不须要比拟，把前面的间接移上去就能够了，这个须要提前断定一下。

贴上代码：

static void Main(string[] args) {
    int[] arr1 = new int[] { 2, 3, 6, 8 };
    int[] arr2 = new int[] { 1, 4, 5, 7 };
    int[] newArr = Sort(arr1, arr2);
    for (int i = 0; i < newArr.Length - 1; i++)
    {
        Console.WriteLine(newArr[i]);
    }

    Console.ReadKey();
}

public static int[] Sort(int[] arr1,int[] arr2)
{
    int[] newArr = new int[arr1.Length + arr2.Length];
    int i = 0, j = 0, k = 0;
    while (i < arr1.Length && j < arr2.Length)
    {
        if (arr1[i] < arr2[j])
        {

            newArr[k] = arr1[i];
            i++;
            k++;
        }
        else
        {

            newArr[k] = arr2[j];
            j++;
            k++;
        }
    }

    while (i < arr1.Length)
        newArr[k++] = arr1[i++];
    while (j < arr2.Length)
        newArr[j++] = arr2[j++];
    return newArr;
}

最初感激一下大佬提供的思路：https://blog.csdn.net/k_koris…

原文链接：https://blog.csdn.net/weixin_…

版权申明：本文为CSDN博主「貂蝉要睡觉」的原创文章，遵循CC 4.0 BY-SA版权协定，转载请附上原文出处链接及本申明。

近期热文举荐：

1.1,000+ 道 Java面试题及答案整顿(2021最新版)

2.别在再满屏的 if/ else 了，试试策略模式，真香！！

3.卧槽！Java 中的 xx ≠ null 是什么新语法？

4.Spring Boot 2.5 重磅公布，光明模式太炸了！

5.《Java开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞+转发哦！