C++面试中的手写快速排序：从基础到最优的完整思考过程

阶段1理解题目要求1-2分钟思考过程确认输入输出请问输入是vector还是数组需要处理空输入吗明确接口需要我实现完整的排序接口还是只需要核心排序逻辑边界确认需要处理重复元素吗对稳定性有要求吗示例对话候选人请问函数签名需要完全按照标准库的sort接口还是可以自定义输入范围是否包含两端 面试官请实现对一个vector的原地排序包含两端索引阶段2写出基础版本5-7分钟基础实现代码代码语言cppAI代码解释// 基础分区函数 int partition(vectorint nums, int left, int right) { int pivot nums[right]; // 选择最右元素作为基准 int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; } } swap(nums[i], nums[right]); return i; } // 基础递归实现 void quickSort(vectorint nums, int left, int right) { if (left right) return; // 递归终止条件 int pivot_pos partition(nums, left, right); quickSort(nums, left, pivot_pos - 1); quickSort(nums, pivot_pos 1, right); }可视化过程代码语言txtAI代码解释初始数组[3, 1, 4, 1, 5, 9, 2, 6] ↑ ↑ left right 分区过程(pivot6): [3,1,4,1,5,2] 6 [9] // 最终i5, 交换6到正确位置阶段3分析复杂度2分钟边写边说的示例这个基础版本的时间复杂度最好/平均情况O(nlogn)最坏情况已排序数组O(n²) 空间复杂度递归栈空间最好O(logn)最坏O(n)阶段4优化实现5-8分钟优化1三数取中法避免最坏情况代码语言cppAI代码解释int medianOfThree(vectorint nums, int left, int right) { int mid left (right - left) / 2; if (nums[left] nums[mid]) swap(nums[left], nums[mid]); if (nums[left] nums[right]) swap(nums[left], nums[right]); if (nums[mid] nums[right]) swap(nums[mid], nums[right]); return mid; } int partition(vectorint nums, int left, int right) { int pivot_idx medianOfThree(nums, left, right); swap(nums[pivot_idx], nums[right]); // 将基准放到最右 // 剩余逻辑不变... }优化2小数组切换插入排序代码语言cppAI代码解释void insertionSort(vectorint nums, int left, int right) { for (int i left 1; i right; i) { int key nums[i]; int j i - 1; while (j left nums[j] key) { nums[j 1] nums[j]; --j; } nums[j 1] key; } } void quickSort(vectorint nums, int left, int right) { if (right - left 16) { // 阈值通常取8-32 insertionSort(nums, left, right); return; } // 剩余逻辑不变... }优化3尾递归优化代码语言cppAI代码解释void quickSort(vectorint nums, int left, int right) { while (left right) { // 改用循环 int pivot_pos partition(nums, left, right); if (pivot_pos - left right - pivot_pos) { quickSort(nums, left, pivot_pos - 1); left pivot_pos 1; } else { quickSort(nums, pivot_pos 1, right); right pivot_pos - 1; } } }阶段5处理边界情况2分钟需要提及的要点处理重复元素可以考虑三向切分(3-way partition)大数处理避免溢出mid left (right - left)/2内存安全验证输入范围有效性