共计 587 个字符，预计需要花费 2 分钟才能阅读完成。
合并两个有序数组，依据题目的条件不同，细节解决也不同。我想先单纯的探讨下合并两个有序数组，不做工夫及空间复杂度的限度。
只合并两个有序数组
这里，只合并两个有序数组，这两个有序数组的长度也只有存储的元素个数那么长。有两种思路，一种是先合并数组，而不论它是否有序，而后将合并之后的数组排序。另一种思路是，在合并数组的过程中，对元素进行排序，合并完结，排序也完结，这种思路借鉴了归并排序的归并过程，即它用到了数组有序这个条件。
一、先将两个数组合并，而后再排序。开拓一个新数组来存储这两个数组中的元素，须要 O(m+n) 的空间复杂度。将两个数组合并，此处不思考这两个数组有序，因而合并数组工夫破费为 O(m+n)，而后排序数组（各种排序都可），这里思考想要较好的工夫复杂度，因而用疾速排序，工夫复杂度为 O((m+n)lg(m+n))，综合起来，最终的工夫复杂度为 O((m+n)lg(m+n))，空间复杂度 O(m+n)。
二、开拓一个新的数组 arr，用来存储这两个有序数组中的元素。这里用到归并排序的 merge 办法，行将两个指针指向两个数组头部，而后比拟指针所指的元素，将较小的元素保留到 arr 数组，并将其指针后移。反复下面的步骤，直到两个数组遍历齐全。这种办法，须要循环 m + n 次，因而工夫复杂度为 O(m+n)，然而因为须要开拓额定的空间来存储这两个数组的元素，因而空间复杂度为 O(m+n)。
正文完
