- 正确答案：快速排序是一种基于分治策略的原地排序算法，核心是partition（分区）操作。它通过选择一个基准元素（pivot），将数组划分为三部分：小于pivot的左子数组、等于pivot的中间段（可选优化）、大于pivot的右子数组；然后递归地对左右子数组排序。最终实现升序排列。 - 解答思路： 1. 输入处理：从控制台读取一行以空格分隔的整数字符串，解析为int数组；支持负数和重复值。 2. 主函数quicksort(arr, low, high)递归调用，边界为low < high。 3. 每次调用先执行partition获取pivot最终位置，再递归排序[low, pivot-1]和[pivot+1, high]。 4. partition采用“双指针+原地交换”方式（Lomuto或Hoare变体），本例使用更稳定且边界清晰的Hoare分区法（避免最坏O(n²)在已排序数组上的退化，但需注意实现细节）。实际工业中常结合三数取中+小数组切换插入排序+尾递归优化。 - 深度知识讲解：【底层原理】快速排序不是简单地“分两半”，而是依赖比较模型下的决策树深度下界Ω(n log n)，其平均性能源于每次partition期望将数组近似二分（数学期望递归深度为~1.39 log₂n）。关键点在于： • pivot选择直接影响时间复杂度：固定选首/尾→最坏O(n²)（如已排序输入）；随机化选pivot→期望O(n log n)，概率保证强；三数取中（取首、中、尾三者中位数）→对常见模式（如部分有序）鲁棒性提升。 • 原地分区必须保证稳定性不被破坏？错！快排本质不稳定——相同值因pivot交换可能改变相对顺序（例如[3a, 2, 3b]中3a与3b在partition中被交换位置）。这是由交换操作不可逆导致的，与归并排序的稳定合并有本质区别。 • 尾递归优化：将较大子数组递归调用改为循环，较小的子数组用递归，可将栈空间从O(n)压至O(log n)。因为递归深度取决于较小子问题规模，每次至少砍掉一半。 • 实际工程优化：当子数组长度≤10时切换为插入排序（常数因子更小）；使用迭代+显式栈替代递归避免栈溢出；Java Arrays.sort()对基本类型用双轴快排（Dual-Pivot Quicksort），将pivot扩展为两个，划分成三段，理论加速约10%。【数据结构视角】 partition过程本质上是在维护两个不变式： - 左指针i左侧所有元素 ≤ pivot - 右指针j右侧所有元素 ≥ pivot 当i与j相遇时，该位置即pivot的最终落点（需再与pivot交换）。此过程无额外空间，仅O(1)辅助变量，体现“原地”特性。【边界与鲁棒性】需处理：空数组、单元素、全相同元素（此时partition若不处理相等情况会无限循环）、整型溢出（本题不涉及，但大规模索引需用long防mid计算溢出）。 - 代码示例（C++风格伪代码，含完整输入输出及三数取中+尾递归优化）： ``` #include #include #include #include #include #include int partition(std::vector& arr, int low, int high) { // 三数取中：取low, mid, high对应值的中位数，并放到high位置作为pivot int mid = low + (high - low) / 2; if (arr[mid] < arr[low]) std::swap(arr[low], arr[mid]); if (arr[high] < arr[low]) std::swap(arr[low], arr[high]); if (arr[high] < arr[mid]) std::swap(arr[mid], arr[high]); std::swap(arr[mid], arr[high]); // pivot放在末尾 int pivot = arr[high]; int i = low - 1; // 小于等于区间的右边界 for (int j = low; j < high; ++j) { if (arr[j] <= pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quicksort_recursive(std::vector& arr, int low, int high) { while (low < high) { int pivot_idx = partition(arr, low, high); // 尾递归优化：先处理较小的子区间，大的用循环，小的用递归 if (pivot_idx - low < high - pivot_idx) { quicksort_recursive(arr, low, pivot_idx - 1); low = pivot_idx + 1; } else { quicksort_recursive(arr, pivot_idx + 1, high); high = pivot_idx - 1; } } } void quicksort(std::vector& arr) { if (arr.size() <= 1) return; quicksort_recursive(arr, 0, arr.size() - 1); } int main() { std::string line; std::getline(std::cin, line); std::stringstream ss(line); std::vector nums; int x; while (ss >> x) { nums.push_back(x); } quicksort(nums); for (size_t i = 0; i < nums.size(); ++i) { if (i > 0) std::cout << " "; std::cout << nums[i]; } std::cout << std::endl; return 0; } ``` - 扩展知识：若面试官追问“如何使快排稳定？”，需明确回答：标准快排无法在O(1)额外空间下保持稳定；若必须稳定，应改用归并排序（O(n)空间）或“稳定快排”变种（如记录原始下标+自定义比较器，但失去原地性）；或者使用std::stable_sort（通常为混合算法：小数组插入+大数组归并）。另外，快排的缓存不友好性（随机访问导致cache miss多）也是其在超大数据集上有时慢于堆排序或归并排序的原因，现代CPU架构下，Timsort（Python/Java TimSort）因利用局部有序性而更优。

百度大模型日常实习一面凉经分享

全站热榜

创作者周榜