企业官网建设流程全解析

“两个数组合并排序”，这六个字可能是很多新手的第一个“噩梦”，也可能是某个深夜加班的最后一根稻草。面试的时候它叫“合并两个有序数组”，工作中它叫“归并两个数据源”，考试的时候它叫“利用归并排序的思想”——名字换了一堆，核心永远都是同一个。

这篇文章我用从业者的视角，把这个最简单的算法题拆到骨头里。你不仅能拿到可直接抄走的代码，更能理解每一步操作背后的“为什么”，学会在不同语言、不同场景下怎么灵活变通。无论是准备面试、应付考试，还是写业务代码时遇到数据合并，看完这篇你都能心里有底。

1. 两个数组合并排序：问题本质与场景拆解

1.1 先说清楚问题本身

题目可以描述成一句话：给你两个数组，把它们合并成一个数组，并且保证结果是升序（或者降序）排列。

这里有个容易被忽略的细节——题目描述里往往藏着“有序”两个字。比如“给你两个已经排好序的数组”，甚至有的题目直接写“两个有序数组”。有没有这两个字，解法完全不同。

先看具体例子：

数组A = [1, 3, 5, 7] 数组B = [2, 4, 6, 8] 合并排序后 = [1, 2, 3, 4, 5, 6, 7, 8]

这个结果看起来平平无奇，但它是“归并排序”这个重要算法的最基础单元。归并排序为什么能在各种排序算法里稳坐头部梯队？靠的就是它。整个归并排序可以形象地理解为：先把数组切成零碎小块，再不停地“两两合并”，每次合并都保证结果有序，最后整体有序。

除了面试和算法竞赛，这种操作在真实业务里也到处都是。比如：

• 数据库里两个表的记录有序合并，本质就是两个有序数组的归并。
• 外部排序（处理放不下内存的大文件）时，把磁盘上的多个有序临时文件合并成一个有序大文件，一样是这个套路。
• 后端服务从多个数据源各取一批增量数据，拿到手后合并去重再统一处理，底层也是这一套。

说白了，只要涉及“多个有序集合拼成一个有序集合”，都跑不掉这个方法。

1.2 有序和无序，两个世界的解法

咱们先分清楚两种情况，因为很多人一上来就用错方法。

第一个情况：两个数组无序。比如A = [5, 1, 4]，B = [3, 2]。这种最简单粗暴的做法是先把两个数组合成一个新数组，然后对整个新数组做一次排序。C语言里可以用qsort，JavaScript里直接concat再sort，Python里+再sort()。时间复杂度取决于你用的排序算法，一般是O((n+m)log(n+m))。

第二个情况：两个数组各自有序。题目只要稍微加“有序”两个字，就意味着你可以把效率提升到O(n+m)——这是质的飞跃。因为两个数组都已经有序，你不需要重新全局排序，只需要用“双指针”一路比对、一路合并就行，每个元素只被扫描一次，高效得可怕。

很多人在这一点上犯糊涂：明明“合并后排序”这种办法写起来更简单，为什么非要学复杂的双指针？答案就藏在大数据量里。假设你有两个各含100万条记录的数组，O((n+m)log(n+m)) 和 O(n+m) 的差距会被拉到数倍甚至数十倍。在实际的业务场景里，这个差距直接决定接口是50毫秒返回还是3秒超时。

所以，核心问题永远是：**给你的数组是不是有序的？**搞清楚前提，才能选对工具。

2. 双指针归并：排序合并的核心算法

2.1 双指针思路的直观理解

双指针的思路，用一句话概括就是：两个数组各自站一个指针，谁小谁先进结果数组，然后对应的指针往前走一步，直到一边先走完，另一边全倒进去。

生活化类比：两摞按身高排好的扑克牌，桌面上摆好最终区。每次只看两摞最上面的那张牌，把较小的那张取走放到结果区。谁小了取谁，取完露出下一张，继续比。最后某摞空了，直接把另一摞剩下的牌依次放进去，收工。

不追求绝对严谨的情况下，这个流程可以用下面这段C语言代码描述：

void merge(int a[], int aLen, int b[], int bLen, int result[]) { int i = 0, j = 0, k = 0; // 两个指针都没走到头就继续比 while (i < aLen && j < bLen) { if (a[i] <= b[j]) { result[k++] = a[i++]; } else { result[k++] = b[j++]; } } // 把a里剩下的元素接上 while (i < aLen) { result[k++] = a[i++]; } // 把b里剩下的元素接上 while (j < bLen) { result[k++] = b[j++]; } }

这段代码是所有后续变体的地基。你不需要背它，你需要理解它背后的运行轨迹。我建议你拿一张纸，把两个数组写下来，然后用手指当指针一步步模拟一遍，比看任何讲解都管用。

2.2 为什么是O(n+m)：复杂度背后的直觉

从代码能看出来，每轮while循环里，要么i往前走一步，要么j往前走一步，要么就进入某个数组的收尾循环。整个过程中，数组A的每个元素被访问一次，数组B的每个元素被访问一次，共访问n+m次，所以时间复杂度是O(n+m)。

空间复杂度要看你把结果放哪。如果开了额外数组来存结果，空间复杂度是O(n+m)；如果允许直接原地利用数组的尾部空位，空间复杂度可以降到O(1)。这部分后面专门说。

有必要单独强调一下“稳定”这个概念。归并过程里当两个元素相等时，我们选择先取A的值，这意味着相等的元素仍然能保持它们在原数组中的相对顺序，这种排序算法叫“稳定排序”。比如排序对象是对象数组，先按时间排序，再按ID稳定排序，那最终ID相同的记录仍然保持时间顺序，这个特性在很多业务里非常有用。

3. 多种语言实现对照与选择建议

3.1 JavaScript：不要无脑concat加sort

JavaScript里，新手最常见的写法是这样的：

function mergeArrays(arr1, arr2) { return arr1.concat(arr2).sort((a, b) => a - b); }

代码没错，结果也对。问题在于sort底层通常是快排，复杂度是O((n+m)log(n+m))，数据量小的时候完全没感觉，数据量上了几十万之后就开始心跳加速。

如果两个数组本身是有序的，双指针写法是更好的选择：

function mergeSorted(arr1, arr2) { const result = []; let i = 0, j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] <= arr2[j]) { result.push(arr1[i++]); } else { result.push(arr2[j++]); } } while (i < arr1.length) result.push(arr1[i++]); while (j < arr2.length) result.push(arr2[j++]); return result; }

推荐指数上，小数据量（几十条）无脑concat + sort完全没问题，但既然你追求的是“掌握核心方法”，建议直接记住双指针版本。顺便提一句，JavaScript里还有个TypedArray相关的set方法，适合处理二进制数据流的合并，但那属于特殊场景，不展开。

3.2 Python：切片、heapq、双指针三选一

Python新手最自然的写法：merged = sorted(a + b)。

只要数据规模可控，这完全没问题。但如果你处理的是大规模有序流式数据，Python标准库heapq提供了更优雅的工具——heapq.merge。它接收多个有序可迭代对象，返回一个合并后的迭代器，内存友好，适合处理无法一次性载入内存的数据。

import heapq a = [1, 3, 5] b = [2, 4, 6] merged = list(heapq.merge(a, b))

不过heapq.merge处理大量有序序列时的底层逻辑，本质还是堆排序和多路归并的结合，它比单纯双指针更灵活之处在于能同时合并多个序列。手写双指针版本则是基础功：

def merge(a, b): i = j = 0 result = [] while i < len(a) and j < len(b): if a[i] <= b[j]: result.append(a[i]) i += 1 else: result.append(b[j]) j += 1 result.extend(a[i:]) result.extend(b[j:]) return result

3.3 Java与C：面试手撕代码的常用战场

Java的Arrays.sort干不了“两路有序直接合并”的活，它只会全量排序，所以面试时手写归并是逃不掉的。Java版本无非是把C的指针换成下标，写法几乎一模一样：

public int[] merge(int[] nums1, int m, int[] nums2, int n) { int[] result = new int[m + n]; int i = 0, j = 0, k = 0; while (i < m && j < n) { result[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++]; } while (i < m) result[k++] = nums1[i++]; while (j < n) result[k++] = nums2[j++]; return result; }

这里我还想提一个极具代表性的面试题变体——LeetCode 88题“合并两个有序数组”。它要求在nums1里原地合并，不允许返回新数组，两个数组的有效长度是m和n，但nums1的长度是m+n，后面已经预留了空位。很多人在原地合并时从头开始操作，结果把nums1还没处理的元素覆盖了。正确做法是从后往前填充：

public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int j = n - 1; int k = m + n - 1; while (i >= 0 && j >= 0) { if (nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } while (j >= 0) { nums1[k--] = nums2[j--]; } }

从后往前递归地利用尾部的空余空间，是原地合并类问题的经典套路。它解决的核心问题是“不额外开新数组、不覆盖未处理的元素”。只要看到题目说“原地操作”“空间复杂度O(1)”，第一反应就应该是倒着处理。

3.4 链表版本：合并两个有序单链表

热词里有人搜“合并两个有序的单链表”，这是同一个问题的链表版。核心思路一样，但操作细节变了，因为链表不能随机访问，只能用指针一个一个接。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; dummy.next = NULL; struct ListNode* tail = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; return dummy.next; }

注意这里用了一个很小的技巧：dummy哨兵节点。如果用普通节点，每次追加都得判断头节点是否为空，代码会啰嗦很多。用哨兵节点可以让头节点的处理和其他节点统一，这是个非常实用的小技巧，写链表题时能省很多心。

4. 变体与进阶：去重、原地排序与多路归并

4.1 合并后去重：两种情况分清楚

很多人问“合并排序要不要去重”，答案取决于题目描述。如果明确说“结果中不含重复元素”，那就需要在合并时顺手去重。实现方案不复杂：比较时如果a[i]和result[k-1]相等，就跳过a[i]，只推进指针，不写入结果。如果两边元素相等，取其中一个、另一个跳过。

也可以先合并再去重，但不推荐——先合并再扫描去重的时间复杂度虽然同样是O(n+m)，但多了一轮全量遍历，空间占用也更大。最容易理解的去重写进合并循环里：

def merge_unique(a, b): i = j = 0 result = [] while i < len(a) and j < len(b): if a[i] < b[j]: result.append(a[i]) i += 1 elif a[i] > b[j]: result.append(b[j]) j += 1 else: # 相等，只取一个 result.append(a[i]) i += 1 j += 1 result.extend(a[i:]) result.extend(b[j:]) return result

这个版本“顺手去重”的关键在于，两个数组各自有序，重复只会发生在相同位置附近，不会跨越很远，所以双指针依然能准确识别。

4.2 原地合并：不开新数组的“倒插法”

前面讲Java的LeetCode 88时已经展示了一版从后往前的原地合并。原理再拆一下：两个数组总共m+n个元素要放进nums1里，nums1末尾恰好有n个空位。如果从头开始正着放，前面刚放完的结果可能还没被处理完就覆盖掉后面还没读到的原始值；但如果从尾部开始放，因为每个位置最终都会被填上，且填入时只取两个数组里当前较大的那个，所以不会覆盖任何还没处理的元素。

原地归并的深刻意义在于，它把空间复杂度从O(n+m)降到了O(1)。这在嵌入式开发、内存受限场景里不是锦上添花，而是硬性要求。

4.3 多路归并：从两个数组到K个数组

当你手里不是两个有序数组，而是10个、100个有序数组时，双指针直接退化成“每次找K个指针中最小的那个”，然后把这个最小值放入结果。如果K很大，每次找最小值都扫描一遍就是O(K)的代价，整体复杂度过高。更科学的做法是把每个数组的当前元素放进一个小顶堆（优先队列），每次从堆顶取最小值，然后把这个数组的下一个元素推进堆里。这样每次取最小值的复杂度从O(K)降到了O(logK)，整体复杂度接近O(n log K)。

Python的heapq.merge支持传入多个可迭代对象，正是多路归并的标准实现。Java的PriorityQueue就是干这个的。实际业务中，比如多分片数据库的合并查询、搜索引擎的倒排索引合并，都是这个思路的工程化应用。

4.4 特殊技巧：C语言的指针数组与字符串数组

热词里出现了“指针数组存放字符串”“C语言数组指针移动指定位输出字符”，虽然这看起来像是在问底层细节，但也确实是合并排序过程中C/C++程序员最容易栽的地方。

在C语言里，如果你要合并的不是int数组，而是一组字符串指针，那么你比较的应该是字符串内容，而不是指针本身。直接比较指针变量会按地址大小排，结果毫无意义。正确用法是strcmp：

#include <string.h> if (strcmp(a[i], b[j]) <= 0) { result[k++] = a[i++]; } else { result[k++] = b[j++]; }

同理，按中文拼音排序需要locale支持，按自定义规则（比如忽略大小写）排序需要写自己的比较函数。这些看起来是小问题，但实际工程里非常容易踩坑。把“指针数组”和“排序”放在一个搜索词里，八成就是遇到了这种问题。

5. 常见问题与排查技巧实录

5.1 为什么我的合并结果不是有序的？

排查方向很明确：先确认输入的两个数组本身是否有序。有人拿[3, 1, 2]和[5, 4]直接跑双指针，结果必然是乱的。双指针归并的前提是“输入各自有序”，除非题目允许你先排序。

另一种情况：自定义排序规则用反了。在JavaScript里sort((a, b) => b - a)是降序，但你合并时用的还是升序判断，两边规则不一致就会乱。所有比较操作必须使用同一个排序规则。

5.2 边界条件之数组为空、长度不等

这是最经典的低级错误。双指针循环结束条件是i < aLen && j < bLen，循环结束后还得手动处理剩余元素。漏掉那两段收尾代码，你得到的结果就永远缺一部分。

另一个边界问题是一开始某个数组就是空数组。这种情况必须在入口加判断：

if not a: return b if not b: return a

虽然不加也能跑（主循环直接跳过，收尾循环把另一个数组全拷进去），但显式判断会让代码意图更清晰。

5.3 指针越界与数组下标错乱

C语言里最容易犯的错是while (i <= aLen)写成了<=，导致越界读了一个不存在的元素。记住你的指针只允许走到aLen - 1，因此条件是i < aLen。这类越界在大型数组上可能不会立刻崩溃，但会引入随机值，排错时非常抓狂。

另一个常见错误是result[k++]和result[++k]的混用。前者是“先赋值再把下标加1”，后者是“先把下标加1再赋值”。归并代码里普遍应该用前者，++k会把结果数组的第一个位置空出来。

5.4 从数组到其他领域的“合并”迁移

热词里出现了“git分支合并”“svn merge代码合并”“maven本地仓库合并”“7z.001文件合并”“B站视频音频合并”“CAD图纸合并”，这些看似八竿子打不着的词，本质上都共享一个心智模型：把分散的多个有序单元，按照某种既定规则统一整理成一个整体。

比如git merge不要求两个分支的提交历史都是线性的，但合并结果一定是顺序化的快照；maven本地仓库合并只是把两个文件夹的内容搬到一起并处理冲突；7z.001分卷压缩文件合并则纯粹是把二进制分块按顺序拼回完整文件。理解“归并”的思维框架后，你会发现迁移到这些领域非常自然。

不过核心算法层面，真正值得你反复手写的还是“两个有序数组”这件事。它是一切多路合并的基础，也是最值得花时间打磨熟练度的基本功。

6. 实战经验与更进一步的学习方向

6.1 双指针不只是用于合并排序

在数组、链表、字符串类问题里，“双指针”是一大类算法的统称。合并排序用的叫“双指针归并”，还有“快慢指针”（判断链表是否有环）、“左右对撞指针”（有序数组的Two Sum）、“滑动窗口”（子数组问题）。三个字概括就是：双向夹逼、一快一慢、同向移动。理解“谁小移谁”“谁满足条件移谁”这些规则后，双指针家族的问题会越刷越顺手。

6.2 归并排序的完整实现：自上而下的递归与自底向上的迭代

既然已经掌握了合并两个有序数组，再往前一步就是亲手实现完整归并排序。

递归版本核心就两步：先把数组对半拆到不可再拆，然后逐层归并。代码结构可以记成“分解-递归-合并”三个动作。

非递归版本（自底向上）更偏向工程实现，它先把数组拆成长度为1的块，相邻两块两两归并，得到长度2的块，再两两归并，直到只剩一块。这种写法避免了递归栈空间，在某些场景（比如处理链表排序）格外好用。

完整实现如下：

void mergeSort(int arr[], int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr + left, mid - left + 1, arr + mid + 1, right - mid, temp + left); }

注意这里mid的计算用left + (right - left) / 2而不是(left + right) / 2，在大量数据时能避免整数溢出，这是老手才有的习惯。

6.3 扩展：SQL里的“合并排序”与MERGE

热词里还有“mysql排序”“跨表合并”，数据库里的排序归并本质上也是在跑归并算法。ORDER BY底层如果用到归并排序，会和数据库缓冲区打交道；多表UNION可以视作把多个结果集合并成一个结果集再进行排序去重。理解最底层的归并逻辑之后，再回看数据库优化器的执行计划，很多行为都在意料之中。

另外Excel的“跨表合并”和数据清洗里的“合并单元格填充”，虽然操作概念不同，但它们都在处理一个核心问题：多个来源的乱序数据，如何在统一规则下重新组织。底层都是同一套“稳定归并 + 去重 + 有序聚合”的思维。

6.4 性能调优与代码风格建议

如果合并的数据量极大，常规的result.push往数组尾部追加可能是性能瓶颈。在JavaScript里预分配数组长度，或者用this“原地写”都可以避免动态扩容的开销。在C里用memcpy批量拷贝整段剩余数据，当然前提是内存连续。

代码风格方面，给出来的例子都刻意保持了清晰命名：i、j分别代表两个源数组的游标，k代表结果数组的游标。面试时写出这种代码，面试官一眼就能看出你对归并的理解程度。比“把所有变量都命名成temp”的代码成熟太多了。

6.5 从竞赛题到业务题的思考方式

竞赛场上，输入规模、时间限制都很明确，你可以放心用最苛刻的算法；业务代码里，数据规模可以被预测，代码的可读性、稳定性往往比极致性能重要。比如接口只需要合并几千条数据，那a.concat(b).sort()完全够用，硬上双指针反而让维护成本变高。学会判断“什么时候该用严肃算法，什么时候能用表达式糊弄过去”，才是一个工程师从写代码到做工程的本质区别。

7. 结语与避坑心得

最后分享几条这些年踩坑攒下的心得。

第一，始终先确认输入前提。题目没提有序，默认当它无序处理；提了有序，优先双指针。拿到题目先别动手写代码，把输入条件、输出要求、空间限制这三件事确认完，再想解法。

第二，边界条件永远是第一优先级。空数组、一个数组为空、两个数组等长、一个数组非常长、全是重复元素、全是负数和零，这些测试用例要在提交之前就自己跑一遍。我在工作里见过太多质量事故，追根溯源就是边界case没处理干净。

第三，手写伪代码比背代码更可靠。一旦理解了“谁小谁进、谁空谁停、剩者全收”这三句话，任何变体你都能现场推出来。我教团队新人时从来不让他们背代码，而是让他们在白板上画数组、画指针、画步骤，画完自然就会了。

这个内容后续你可以沿着两条线扩展：往深度走，去刷归并排序、逆序对、海量数据外部排序；往广度走，去理解多路归并、数据库执行计划、分布式系统中的数据shuffle。所有复杂系统里的“有序合并”，底下都是你最早学到的这段双指针代码。

两个数组合并排序，入门简单，但值得你反复琢磨。不要因为它太基础就跳过，很多高级算法的根，就长在这六字最普通的描述里。