软考-软件设计师：排序算法-归并排序 作者：马育民 • 2025-04-15 08:51 • 阅读：10006 # 归并排序 归并也称为 `合并`，是将 **两个 或 两个以上** 的有序子表 **合并成一个** 新的有序表。 若将两个有序表合并成一个有序表，则称为 **二路合并** ### 例子 每次合并时，比较大小，比如：将小的放在前面 [](https://www.malaoshi.top/upload/0/0/1GWwieCMVAN.png) 参考： https://blog.csdn.net/justidle/article/details/104203958 ### 合并两个有序数组流程 如上图中的最后一次合并，要将 `[4,5,7,8]` 和 `[1,2,3,6]` 两个已经有序的子序列，合并为最终序列 `[1,2,3,4,5,6,7,8]`，步骤如下： [](https://www.malaoshi.top/upload/0/0/1GWwib1XhtA.png) 参考： https://blog.csdn.net/justidle/article/details/104203958 ### 时间复杂度 ``` O(nlog₂n) ``` 执行 `log₂n` 趟，每趟比较 `n` 次（不到 `n` 次） ### 空间复杂度 0(n) 在排序过程中仅需要一个元素的辅助空间用于数组元素的交互 ### 是否稳定 稳定 # 题 两个递增序列 A 和 B 的长度分别为 `m` 和 `n`（`m<n` 且m与n接近），将二者归并为一个长度为 `m+n` 的递增序列。当关系为（）时，归并过程中元素的比较次数最少。 [](https://www.malaoshi.top/upload/0/0/1GWwiqM2zNv.png) ### 分析 选项A，当 `b1` 比 A 所有元素大时，就不需要比较了，前面有 `m` 个 `a`，即：比较 `m` 次 选项B，当 `a1` 比 B 所有元素大时，就不需要比较了，前面有 `n` 个 `b`，，即：比较 `n` 次 选项C，当 `bm` 比 `am`大时，就不需要比较了，前面有 `m` 个 `a`，`m-1` 个 `b`，即：比较 `m + m - 1 = 2m - 1` 次 选项D，当 `bm+1` 比 `am`大时，就不需要比较了，前面有 `m` 个 `b`，和 `m` 个 `a` ，即：比较 `2m` 次 ### 答案 题中给出 `m<n`，所以选择 A 参考： https://blog.csdn.net/justidle/article/details/104203958 原文出处：http://malaoshi.top/show_1GWwqGH7DD9.html