美团一面：两个有序的数组，如何高效合并成一个有序数组？

太过爱你忘了你带给我的痛 2022-08-28 05:45 117阅读 0赞

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

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

乍一看跟递归思想很像，确实如此，分治思想一般就是使用递归来实现的。但是需要注意的是：递归是代码实现的方式，分治属于理论。

接下来看一副图理解下：

![20211017174322704.png][]

说完它的思想：我们再来分析下时间复杂度。归并算法采用的是完全二叉树的形式。所以可以由完全二叉树的深度可以得知，整个归并排序需要进行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;
    }

说完了归并算法回到题目上来 首先分析下 题目给定的是两个已经排好序的数组合并，关键字“合并”，“两个”，正好符合我们的归并算法，并且已经分类好了，只需要去合并就可以了。

来看下几张图。

![20211017174323293.png][]

蓝色的箭头表示最终选择的位置，而红色的箭头表示两个数组当前要比较的元素，比如当前是2与1比较，1比2小，所以1放到蓝色的箭头中，蓝色的箭头后移，1的箭头后移。

![2021101717432419.png][]

然后2与4比较，2比4小那么2到蓝色的箭头中，蓝色箭头后移，2后移，继续比较.......

![20211017174324497.png][]

归并思路就是这样了，最后唯一需要注意的是那个先比较完的话，那么剩下的直接不需要比较，把后面的直接移上去就可以了，这个需要提前判定一下。

贴上代码：

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/article/details/80508543][https_blog.csdn.net_k_koris_article_details_80508543]

原文链接：[https://blog.csdn.net/weixin\_40097554/article/details/108656165/][https_blog.csdn.net_weixin_40097554_article_details_108656165]

**近期热文推荐：**

1.[1,000+ 道 Java面试题及答案整理(2021最新版)][1_000_ _ Java_2021]

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

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

4.[Spring Boot 2.5 重磅发布，黑暗模式太炸了！][Spring Boot 2.5]

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

觉得不错，别忘了随手点赞+转发哦！

[20211017174322704.png]: /images/20220828/4d5a921a5eac45829b94a41a135702b3.png
[20211017174323293.png]: /images/20220828/17e1ee3f08a845d3b9fb102f5a1bfc68.png
[2021101717432419.png]: /images/20220828/0a7f6644768b43f08f92966e99aa3baf.png
[20211017174324497.png]: /images/20220828/6493b3536bd148c3aa3d5612a8bb4c90.png
[https_blog.csdn.net_k_koris_article_details_80508543]: https://blog.csdn.net/k_koris/article/details/80508543
[https_blog.csdn.net_weixin_40097554_article_details_108656165]: https://blog.csdn.net/weixin_40097554/article/details/108656165/
[1_000_ _ Java_2021]: https://www.javastack.cn/mst/
[if_ else]: https://www.javastack.cn/article/2021/strategy-pattern-instead-of-if-else/
[Java _ xx _ null]: https://www.javastack.cn/article/2021/intellij-idea-ligatures-settings/
[Spring Boot 2.5]: https://www.javastack.cn/article/2021/spring-boot-2.5-released/
[Java]: http://www.javastack.cn/article/2020/alibaba-release-java-develop-rules-songshan/