- 正确答案：归并排序是一种基于分治（Divide and Conquer）思想的稳定排序算法，其核心过程分为三步：分解（Divide）、解决（Conquer）、合并（Combine）。它将待排序数组递归地二分拆解为单元素子数组（此时每个子数组天然有序），再自底向上两两归并（merge）已排序的子数组，最终得到完整有序数组。时间复杂度恒为 O(n log n)，空间复杂度为 O(n)，属于典型“以空间换时间”的算法。 - 解答思路： 1. 分解：递归地将数组从中间切分为左右两个子数组，直到子数组长度 ≤ 1（递归基）； 2. 解决：由于长度为 0 或 1 的数组天然有序，无需处理，直接返回； 3. 合并：将两个已排序的左右子数组，通过双指针（i 指向左半部分起始，j 指向右半部分起始）逐个比较元素大小，将较小者复制到临时辅助数组中，最后将剩余未复制完的一侧全部追加； 4. 将临时数组中归并好的结果拷贝回原数组对应区间（关键：归并操作必须作用于原数组的指定范围，而非全局）。注意：归并排序通常采用“自顶向下”递归实现，但也可用“自底向上”迭代实现（避免递归栈开销）；实际工程中常结合插入排序优化小规模子数组（如 n ≤ 16 时改用插入排序），减少递归与函数调用开销。 - 深度知识讲解：（1）稳定性原理：归并过程中，当 left[i] == right[j] 时，优先取 left[i]（即左子数组元素先入结果），保证相等元素的相对位置不变 → 归并排序是稳定排序。这是由合并逻辑中“<=”或“<”的判断条件决定的，若写成 if left[i] <= right[j] 则稳定；若写成 if left[i] < right[j] 仍稳定（因相等时取 right[j] 会破坏稳定性，故必须明确左优先）。（2）内存访问模式：归并排序具有良好的局部性（locality of reference）——合并时顺序扫描左右子数组及辅助数组，缓存命中率高，适合现代CPU架构；但需要额外 O(n) 辅助空间存储合并结果，无法原地排序（in-place）。存在 in-place 归并变种（如 Block Sort、SymMerge），但实现复杂、常数因子大，不具实用价值。（3）递归深度与栈空间：递归版归并排序最坏/平均递归深度为 ⌈log₂n⌉，因此系统栈空间消耗为 O(log n)；若 n 极大（如 10⁹），可能栈溢出，此时应改用迭代版。（4）与快排对比：快排平均 O(n log n) 但最坏 O(n²)，不稳定，原地排序，缓存局部性较差（分区过程跳跃访问）；归并排序严格 O(n log n)，稳定，非原地，缓存友好。在外部排序（如磁盘大数据排序）中，归并是基石（多路归并），因其可流式处理、I/O 友好。（5）底层数据结构依赖：归并排序不依赖特定数据结构，但对随机访问高效（需 O(1) 索引访问），因此天然适配数组；链表版归并排序甚至更优（无需额外空间分配，仅重连指针，空间复杂度 O(log n) 仅用于递归栈），且避免了数组合并时的拷贝开销。 - 代码示例（递归版，C++ 风格伪代码，含详细注释）： ``` // 主入口：对 arr[0..n-1] 排序 void mergeSort(vector& arr) { if (arr.size() <= 1) return; vector temp(arr.size()); // 全局辅助数组，避免每次 merge 重复 new/delete mergeSortHelper(arr, temp, 0, arr.size() - 1); } // 递归辅助函数：对 arr[l..r] 排序，temp 为辅助空间 void mergeSortHelper(vector& arr, vector& temp, int l, int r) { if (l >= r) return; // 递归基：子数组长度为 0 或 1 int mid = l + (r - l) / 2; // 防止整型溢出 mergeSortHelper(arr, temp, l, mid); // 排序左半 [l, mid] mergeSortHelper(arr, temp, mid + 1, r); // 排序右半 [mid+1, r] merge(arr, temp, l, mid, r); // 合并 [l, mid] 和 [mid+1, r] } // 合并 arr[l..mid] 和 arr[mid+1..r] 到 arr[l..r]，使用 temp 辅助 void merge(vector& arr, vector& temp, int l, int mid, int r) { // 步骤1：将 arr[l..r] 复制到 temp[l..r]（避免覆盖） for (int i = l; i <= r; i++) { temp[i] = arr[i]; } // 步骤2：双指针合并 int i = l, j = mid + 1, k = l; // i:左子数组当前索引，j:右子数组当前索引，k:结果写入位置 while (i <= mid && j <= r) { if (temp[i] <= temp[j]) { // 关键：<= 保证稳定性 arr[k++] = temp[i++]; } else { arr[k++] = temp[j++]; } } // 步骤3：复制剩余部分（只会执行其中一个） while (i <= mid) arr[k++] = temp[i++]; while (j <= r) arr[k++] = temp[j++]; } ``` - 补充：迭代版（自底向上）核心逻辑简述：初始化子数组长度 len = 1；当 len < n 时：对每个起始位置 i = 0, 2*len, 4*len, ...：设 left = i, mid = min(i + len - 1, n - 1), right = min(i + 2*len - 1, n - 1)；若 mid < right，则 merge(arr, temp, left, mid, right)； len *= 2；迭代版无递归调用，栈空间 O(1)，适合超大数组或嵌入式环境。 - 常见面试追问点： Q：如何优化空间？→ 答：复用一个全局 temp 数组（如上），避免每次 new；或改用链表版（O(1) 额外空间，仅递归栈）；或实现 in-place 合并（理论可行但工程不推荐）。 Q：能否用于链表排序？→ 答：可以，且更优：无需辅助空间（除递归栈），找中点可用快慢指针，合并即指针重连，时间仍 O(n log n)。 Q：和堆排序比如何？→ 答：归并稳定、缓存友好、易并行（分治天然可并行），堆排序不稳定、原地、缓存差（跳着访问），但堆排序最坏也是 O(n log n)，且可做 Top-K 流式处理。

滴滴后端实习二面 55min

全站热榜

创作者周榜