- 正确答案：快速排序是一种原地、不稳定的分治排序算法，核心是通过一次划分（partition）操作将数组分为三个逻辑区域：小于基准值的部分、等于基准值的部分（可选）、大于基准值的部分；然后递归地对左右两个子区间排序。最优实现采用双指针原地交换，时间复杂度平均O(n log n)，最坏O(n²)，空间复杂度O(log n)（递归栈深度，尾递归优化后）。 - 解答思路： 1. 选择一个基准元素（pivot），通常取首/尾/随机索引或三数取中以避免最坏情况； 2. 使用双指针（low 和 high）从两端向中间扫描，维持循环不变式： - arr[low] 左侧（含）所有元素 ≤ pivot； - arr[high] 右侧（含）所有元素 ≥ pivot； - 当 arr[low] > pivot 且 arr[high] < pivot 时，交换二者； 3. 扫描结束后，low 与 high 相遇位置即为 pivot 的最终落点，将其与该位置交换； 4. 递归排序 [left, pivot_index−1] 和 [pivot_index+1, right] 两个子区间； 5. 递归基：当 left ≥ right 时返回。 - 深度知识讲解：（1）原地性与内存局部性：快排仅用 O(1) 额外空间做交换，无额外数组分配，缓存友好，现代CPU流水线效率高；（2）不稳定性根源：相等元素可能因跨区交换而改变相对顺序（如 arr[i]=arr[j]=x，i left and arr[j] > pivot: j -= 1 if i >= j: break arr[i], arr[j] = arr[j], arr[i] # j 是 pivot 最终位置（因为 arr[j] <= pivot，且左侧都 <= pivot） pivot_idx = j # 尾递归优化：先递归处理较小段，大段用循环迭代 if pivot_idx - left < right - pivot_idx: quicksort(arr, left, pivot_idx) left = pivot_idx + 1 else: quicksort(arr, pivot_idx + 1, right) right = pivot_idx - 1 ``` - 扩展知识： • Java Arrays.sort(int[]) 对基本类型使用双轴快排（Dual-Pivot Quicksort），由Yaroslavskiy提出，理论更优常数因子； • C++ std::sort 是 introsort（快排+堆排序+插入排序混合），当递归深度超阈值（2×log₂n）自动切为堆排序，保证最坏 O(n log n)； • 快排的“比较模型”下信息论下界为 Ω(n log n)，故其平均性能已达理论最优； • 在外部排序、分布式排序（如MapReduce中Shuffle阶段的分区）中，快排思想用于数据分片与局部有序保障。

27实习阿里国际算法二面分享

全站热榜

创作者周榜