- 正确答案：以下是一个标准的、原地分区（in-place partition）的快速排序实现，使用递归方式，时间复杂度平均 O(n log n)，最坏 O(n²)，空间复杂度 O(log n)（递归栈深度，理想情况下为平衡分割）。 - 解答思路：快排核心是“分治 + 原地分区”。第一步选基准（pivot），第二步用双指针（或 Lomuto/Hoare 分区方案）将数组划分为三段：[≤ pivot]、[pivot]、[≥ pivot]（注意：Lomuto 通常保证 pivot 落在最终位置；Hoare 更高效但 pivot 位置不固定）。第三步递归排序左右子区间。关键点在于——必须原地操作、避免额外数组分配（否则失去“手撕”意义），且需处理边界（如空/单元素）、重复元素（稳定性不保证，但要正确划分）、以及避免最坏退化（面试中可提优化策略，如随机化 pivot）。 - 深度知识讲解： 1. **分区算法本质**：快排性能完全取决于分区质量。Lomuto 分区（以末尾为 pivot）逻辑清晰但交换次数多；Hoare 分区（首尾双向扫描）交换更少、更适合实际工程，但需注意循环终止条件和边界越界（如 while i < j 与 while arr[i] <= pivot 的组合易导致 i 越界，必须加 i < j 约束）。 2. **递归栈深度与尾递归优化**：最坏情况下（每次 pivot 极值）递归深度为 O(n)，可能导致栈溢出。可通过“小数组插排 + 大数组快排 + 尾递归优化（先递归小半边，再用 while 循环处理大半边）”将最坏栈空间压至 O(log n)。 3. **重复元素处理**：基础快排对大量重复元素退化为 O(n²)（如全相同数组）。工业级实现（如 Java Arrays.sort() 对 int 使用 Dual-Pivot Quicksort，Python timsort 对小数组混合插入+归并）会引入三路快排（Dutch National Flag）：划分成 < = > 三段，时间复杂度稳定为 O(n) 当所有元素相等。 4. **底层内存视角**：原地排序意味着所有操作在原始数组的连续内存块内完成，无 heap 分配（除递归栈外），缓存友好（局部性好）；而新建数组的版本（如示例伪代码中的 less/greater）会产生 O(n) 额外空间和多次内存拷贝，违背“手撕”考察意图。 5. **稳定性与比较器**：快排是不稳定排序（相同元素相对顺序可能改变），因其交换不基于原始索引。若需稳定，应选归并排序或改造为索引排序（排序索引数组，用原数组做比较依据）。 - 代码示例（Lomuto 分区，带随机化 pivot 防最坏，C++ 风格但纯文本）： ``` #include void swap(int& a, int& b) { int t = a; a = b; b = t; } int partition(vector& arr, int low, int high) { // 随机化 pivot：避免已排序输入退化 random_device rd; mt19937 g(rd()); uniform_int_distribution dist(low, high); int rand_idx = dist(g); swap(arr[rand_idx], arr[high]); // pivot 放末尾 int pivot = arr[high]; int i = low - 1; // i 指向 <= pivot 区域的右边界 for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); // pivot 归位 return i + 1; } void quicksort(vector& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); // pi 是 pivot 最终下标 quicksort(arr, low, pi - 1); // 左子数组 quicksort(arr, pi + 1, high); // 右子数组 } } // 调用入口 void sort(vector& arr) { if (arr.size() <= 1) return; quicksort(arr, 0, arr.size() - 1); } ``` - 扩展提醒（面试加分点）： • 若面试官追问“如何进一步优化”，可答：① 当子数组长度 < 10 时切到插入排序（减少小数组递归开销）；② 使用 introsort（快排+堆排序兜底，当递归深度超阈值 2×log₂n 时切换为堆排，保证最坏 O(n log n)）；③ 三路快排处理重复键（partition 返回 lt/gt 边界，递归只处理 < 和 > 区间，= 区间已有序）。 • 若被问“为什么不用 std::sort？”，应回答：手撕考察对算法本质的理解（分区逻辑、递归结构、边界控制），而非调库能力；且自实现可定制（如指定比较器、支持部分排序、嵌入调试钩子等）。 • 常见手撕错误：忘记递归终止条件（low >= high）、分区后未排除 pivot 下标（如 quicksort(..., pi, ...) 导致死循环）、随机化写在函数内导致每次调用 new seed（应复用 generator）——这些都会被面试官敏锐捕捉。

shopee 面经-后端开发（做分布式存储中间件）

全站热榜

创作者周榜