- 正确答案：以力扣第912题“排序数组”为例，要求实现一个时间复杂度为O(n log n)、空间复杂度尽可能优的稳定/非稳定排序算法。推荐手写**归并排序（稳定，O(n)额外空间）** 或 **堆排序（不稳定，O(1)额外空间）**；若面试官强调工程实践与鲁棒性，可先说明标准库sort的底层（如Introsort），再手写归并排序作为核心实现。 - 解答思路：第一步：明确题目约束——输入是int数组，无特殊范围限制（排除计数排序），需通用比较排序；要求中等难度，考察对分治/堆结构的理解深度而非单纯背代码。第二步：排除冒泡/插入（O(n²)超时）、快排（最坏O(n²)，且手写partition易错，稳定性难保证）；优先选择归并排序——逻辑清晰、递归结构直观、边界可控、天然稳定。第三步：拆解归并过程为两个子问题：① 递归分解至单元素（mergeSort函数）；② 合并两个有序子数组（merge函数）。重点在于merge中双指针+临时数组的协作细节，以及索引映射（原数组下标 vs 临时数组偏移）。第四步：优化空间——避免每层都new vector，改用全局临时缓冲区（或传入辅助数组），减少内存分配开销；同时注意闭区间处理（left <= right）和mid计算防溢出（mid = left + (right - left) / 2）。 - 深度知识讲解： ▶ 归并排序底层本质是**完全二叉树的后序遍历**：每个节点代表一次merge操作，叶子为单元素，高度为log₂n，每层总合并耗时O(n)，故总时间O(n log n)。其稳定性源于merge时“左子数组元素优先写入”的策略（当arr[i] == arr[j]，取左半部分元素，保持相对顺序）。 ▶ 内存模型层面：归并需O(n)辅助空间，因合并时必须暂存结果（否则原地覆盖会丢失未处理数据）；而堆排序利用数组的隐式完全二叉树结构（下标i的左孩子为2i+1，右孩子2i+2，父节点(i-1)/2），通过sift-down维护最大堆性质，实现原地排序。但堆排序不稳定——相同值的元素在sift过程中可能被跨距离交换，破坏原始顺序。 ▶ 对比C++ std::sort：实际采用Introsort（混合排序）——初始快排，递归深度超阈值（≈2 log₂n）时切换为堆排序，小数组（如n<16）则用插入排序。该设计兼顾平均性能、最坏保障与缓存友好性，体现工业级权衡思维。 ▶ 扩展考点：若数组含大量重复元素，可引入三路快排（Dutch National Flag partition）优化；若内存极度受限（嵌入式场景），可学Block Sort（块排序）或WikiSort（原地稳定归并，基于循环位移，时间O(n log n)，空间O(1)但常数极大）。 - 代码示例（C++，手写归并排序，带详细注释）： ``` void merge(vector& nums, int left, int mid, int right, vector& temp) { // 将nums[left..right]合并：左右两段已分别有序 int i = left, j = mid + 1, k = 0; // 双指针归并，小者先填入temp while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { // 关键：<= 保证稳定性 temp[k++] = nums[i++]; } else { temp[k++] = nums[j++]; } } // 复制剩余部分（必有一方已空） while (i <= mid) temp[k++] = nums[i++]; while (j <= right) temp[k++] = nums[j++]; // 将temp中[0..k-1]拷回nums[left..right] for (int idx = 0; idx < k; idx++) { nums[left + idx] = temp[idx]; } } void mergeSort(vector& nums, int left, int right, vector& temp) { if (left >= right) return; int mid = left + (right - left) / 2; // 防止(left+right)溢出 mergeSort(nums, left, mid, temp); mergeSort(nums, mid + 1, right, temp); merge(nums, left, mid, right, temp); } vector sortArray(vector& nums) { vector temp(nums.size()); // 复用同一缓冲区，避免递归中重复分配 mergeSort(nums, 0, nums.size() - 1, temp); return nums; } ``` - 补充提醒（面试实战要点）： ① 手写前务必确认输入输出形式（本题是in-place修改还是返回新数组）； ② 边界条件必须显式写出（如if(left >= right) return），不可依赖“默认终止”； ③ 若被问“如何优化空间”，可答：“复用同一temp数组，并通过参数传递而非局部声明”； ④ 若被追问“能否原地归并”，需诚实说明理论可行（如Knuth的循环位移法）但实现复杂，工程中不推荐，此时应转向堆排序方案并手写heapify。

拼多多暑期实习算法一面分享

全站热榜

创作者周榜