- 正确答案：手撕快排是指在面试中不借助IDE、不查资料，徒手写出快速排序的完整可运行代码（通常要求原地排序、使用递归或迭代实现），且代码逻辑正确、边界处理严谨、时间复杂度符合预期（平均O(n log n)，最坏O(n²)）。 - 解答思路：快速排序的核心是“分治 + 原地分区（partition）”。需明确三步： 1）选择基准（pivot）——常用取首/尾/随机/三数取中； 2）将数组划分为三段：[小于pivot][等于pivot][大于pivot]（三路快排更鲁棒）或经典两路：[≤pivot][>pivot]（注意稳定性非必需，但分区必须正确）； 3）递归排序左右子区间。关键难点在于： • 边界条件（如l >= r时return）； • partition函数的双指针实现（避免越界、死循环）； • 基准交换时机（确保pivot最终落于正确终位）； • 优化：小数组切回插入排序、尾递归优化、随机化pivot防退化。 - 深度知识讲解：快速排序本质是基于比较的内部排序算法，其性能高度依赖partition过程的质量。底层原理涉及： • **原地分区的不变式（invariant）**：在双指针法中（如lomuto或hoare分区），需严格维护如下不变式： - lomuto风格（以末尾为pivot）：[0, i]存≤pivot元素，[i+1, j-1]存>pivot元素，j到末尾未处理； - hoare风格（首尾双向扫描）：左指针找≥pivot，右指针找≤pivot，交换后继续，直到指针交错；hoare更高效（交换次数少、对重复元素友好），但终位pivot位置不确定，需额外处理。 • **稳定性与原地性矛盾**：快排天然不稳定（因跨距离交换），若强行稳定需O(n)额外空间（如记录原始下标），违背原地初衷。 • **最坏场景成因**：每次pivot都是极值（如已排序数组选首/尾），导致分区极度不平衡，递归深度O(n)，每层扫描O(n)，总O(n²)。解决方案： - 随机化pivot（Math.random()或Fisher-Yates采样）； - 三数取中（取arr[l], arr[(l+r)/2], arr[r]的中位数作pivot）； - 引入introsort（快排+堆排兜底，当递归深度超2log₂n时切换）。 • **递归栈空间**：最坏O(n)，平均O(log n)；可改写为迭代版（显式用栈存[l,r]区间），避免栈溢出风险。 • **与归并排序对比**：快排cache友好（局部性好，连续访问），归并需O(n)额外空间且随机访问多；但归并稳定且最坏O(n log n)，快排则依赖输入分布。 - 代码示例（推荐hoare分区 + 随机化 + 尾递归优化的工业级手撕版本）： ```java public class QuickSort { public static void quickSort(int[] arr) { if (arr == null || arr.length <= 1) return; quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int l, int r) { while (l < r) { // 尾递归优化：将较大子区间递归，小子区间用循环处理 int p = partition(arr, l, r); if (p - l < r - p) { quickSort(arr, l, p - 1); l = p + 1; // 迭代处理右半 } else { quickSort(arr, p + 1, r); r = p - 1; // 迭代处理左半 } } } private static int partition(int[] arr, int l, int r) { // 随机化pivot：避免最坏情况 int randIdx = l + (int)(Math.random() * (r - l + 1)); swap(arr, randIdx, r); int pivot = arr[r]; int i = l, j = r - 1; // hoare双向指针 while (true) { while (i <= j && arr[i] < pivot) i++; // 左找>=pivot while (i <= j && arr[j] > pivot) j--; // 右找<=pivot if (i >= j) break; swap(arr, i++, j--); } swap(arr, i, r); // pivot放到终位i（此时i是第一个>=pivot的位置） return i; } private static void swap(int[] arr, int i, int j) { if (i != j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } } ``` 补充说明： - 该实现采用hoare分区，循环内i和j在相等时停止（故对重复元素天然鲁棒）； - partition返回pivot最终索引，左右子区间为[l, p-1]和[p+1, r]； - 尾递归优化确保栈空间最坏O(log n)； - 随机化pivot使期望时间复杂度严格为O(n log n)，且对抗恶意输入； - 若面试官要求“最简版”，可用lomuto分区（更易写但稍慢）：pivot固定为arr[r]，单指针i从l-1开始，遍历j∈[l,r-1]，遇≤pivot则++i并swap(arr[i],arr[j])，最后swap(arr[i+1],arr[r])，返回i+1。扩展提醒：面试中若被追问“如何处理大量重复元素？”，应立即想到三路快排（Dutch National Flag）——分区为< = >三段，pivot区间不再递归，时间复杂度退化为O(n)当所有元素相等。伪代码核心： lt = l, gt = r, i = l+1; while (i <= gt) { if (arr[i] < pivot) swap(arr[lt++], arr[i++]); else if (arr[i] > pivot) swap(arr[i], arr[gt--]); else i++; }

百度测试开发面试

全站热榜

创作者周榜