- 正确答案：快速排序的手写实现通常采用原地分区（in-place partitioning）方式，以避免额外空间开销。核心是 partition 函数将数组划分为三段：[小于 pivot 的元素][pivot][大于等于 pivot 的元素]，然后递归处理左右子区间。以下是标准的、可直接手写的 C++/Java 风格伪代码（兼容面试白板书写习惯，无 STL 依赖，下标闭区间）： void quicksort(int arr[], int left, int right) { if (left >= right) return; int pivot_index = partition(arr, left, right); quicksort(arr, left, pivot_index - 1); quicksort(arr, pivot_index + 1, right); } int partition(int arr[], int left, int right) { // 选择最后一个元素为 pivot（也可用 random 或 median-of-three 提升鲁棒性） int pivot = arr[right]; int i = left; // i 指向下一个待放置「小于 pivot」元素的位置（即 [left, i) 是 < pivot 区间） for (int j = left; j < right; j++) { if (arr[j] < pivot) { swap(arr[i], arr[j]); i++; } } swap(arr[i], arr[right]); // 将 pivot 放到最终位置 i return i; } - 解答思路：手写快速排序需体现三个关键意识： 1）边界控制：递归终止条件必须是 left >= right（单元素或空区间），而非 left == right，否则可能死循环； 2）分区逻辑：使用双指针（i 和 j），j 扫描整个待分区段 [left, right)，i 维护已处理的小于 pivot 的右边界；这是 Lomuto 分区方案，代码简洁、易手写、符合面试预期； 3）pivot 归位：循环结束后，pivot（原在 right 位置）与 arr[i] 交换，确保 pivot 落在最终有序位置，且左侧全小、右侧全大（注意：此处是严格 < pivot 左侧，≥ pivot 右侧，故算法不稳定）。 - 深度知识讲解： ① 底层原理：快排本质是分治（Divide-Conquer）+ 原地交换。其效率高度依赖 partition 的平衡性。最坏情况（每次 pivot 极值）导致深度 O(n)、时间 O(n²)，源于递归树退化为链表；平均情况因期望每次分割比例为常数（如 1:9），递归树深度为 O(log n)，每层总扫描 O(n)，故均摊 O(n log n)。 ② 不稳定性根源：swap 操作不保序。例如 [3a, 2, 3b]，若 pivot=3b，当 2<3b → swap(3a,2) 得 [2,3a,3b]，再 swap(3a,3b) → [2,3b,3a]，3a 与 3b 相对顺序翻转。 ③ 内存局部性优势：原地分区仅用 O(log n) 栈空间（递归深度），且访问模式高度连续（j 顺序遍历，i 随机跳但 cache line 友好），远优于归并排序的 O(n) 额外数组。 ④ 工业级优化点（面试加分项）：　• 小数组切换插入排序（如 size ≤ 10）：减少递归开销；　• 三数取中（median-of-three）选 pivot：取 left、mid、right 三者中位数，大幅降低最坏概率；　• 尾递归优化：对较小的子区间递归，较大的子区间用循环处理，将栈空间压至 O(log n) 最坏；　• 重复元素处理：使用三路快排（Dutch National Flag）——分区为 [pivot]，时间复杂度退化为 O(n) 当所有元素相等，避免 O(n²)。 - 三路快排 partition 伪代码（补充，体现深度）： int[] threeWayPartition(int arr[], int left, int right) { int pivot = arr[left]; int lt = left, gt = right, i = left + 1; // lt: pivot 最左索引 while (i <= gt) { if (arr[i] < pivot) { swap(arr[lt++], arr[i++]); } else if (arr[i] > pivot) { swap(arr[i], arr[gt--]); } else { i++; } } return new int[]{lt, gt}; // [left, lt) pivot } - 常见手写错误预警（面试官重点观察）： × 忘记递归终止条件（无限递归）； × partition 中 j 循环写成 j <= right（越界访问 pivot 自身）； × swap 后未更新 i（导致重复交换或漏交换）； × 返回 pivot_index 前未执行 final swap（pivot 未归位，递归错乱）； × 使用 arr[0] 作为 pivot 却未做边界检查（left>0 时非法）。该实现满足校园招聘对基础算法手写能力的核心要求：逻辑自洽、边界严谨、可读性强、具备优化意识。

腾讯前端一面面经

全站热榜

创作者周榜