- 正确答案：手撕快排是指在面试中不借助IDE、不查资料，徒手写出快速排序的完整可运行代码（通常为原地分区版本），要求逻辑清晰、边界正确、无明显bug。标准实现应包含partition分区函数和quicksort递归主函数，使用双指针（Lomuto或Hoare分区方案均可，但Hoare更高效且更贴近底层原理）。 - 解答思路：第一步：明确目标——实现原地、非稳定、平均O(n log n)的排序，避免额外空间（不能用类似Python列表推导式生成新数组的方式）。第二步：选择分区策略。推荐Hoare分区法，因其交换次数更少、对重复元素更鲁棒、且能自然支持双向收缩，体现对指针操作和循环不变式的理解。第三步：定义递归边界——当left >= right时返回，避免越界和空区间处理错误。第四步：在partition中维护两个指针i（从左向右找>=pivot的元素）、j（从右向左找<=pivot的元素），相遇即停止；注意while条件中必须先移动指针再比较，否则易陷入死循环或越界（关键细节！）。第五步：递归处理左右子区间：[left, j] 和 [j+1, right]（Hoare方案下，最终j是右子区间的右边界，而非pivot最终位置，这点常被误写为[i, right]导致错误）。 - 深度知识讲解：快排本质是分治（Divide-Conquer）+ 原地分区（In-place Partitioning）。其性能高度依赖partition的质量：理想情况下每次pivot将数组等分，递归深度log n；最坏情况（如已排序数组选首/尾为pivot）退化为O(n²)，故工业级实现必引入优化：（1）三数取中（median-of-three）：取arr[left], arr[mid], arr[right]的中位数作为pivot，大幅降低最坏概率；（2）小数组切换插入排序：当子数组长度≤10时直接插入排序，减少递归开销；（3）尾递归优化：对较大子区间迭代处理，较小的子区间递归，保证栈空间O(log n)；（4）重复元素处理：三路快排（Dutch National Flag）可将数组分为< = >三段，使含大量重复元素时达到O(n)最优时间，其底层基于三个指针low/mid/high维护不变式：[left, low) < pivot, [low, mid) == pivot, [mid, high)未探, (high, right] > pivot。底层数据结构视角：快排不依赖任何高级结构，仅靠数组索引和原地交换，体现对内存局部性（cache-friendly）和指针算术的深刻理解。其swap操作是原子的（通常为3次赋值），而partition过程中的比较与交换顺序直接影响分支预测效率——现代CPU对有序数据分支预测准确率高，但快排本身会打乱局部性，因此实际性能还受CPU流水线、缓存行大小（64字节）影响。 - 代码示例（Hoare分区 + 三数取中 + 尾递归优化 + 小数组插入排序）： ``` def insertion_sort(arr, left, right): for i in range(left + 1, right + 1): key = arr[i] j = i - 1 while j >= left and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key def median_of_three(arr, left, right): mid = left + (right - left) // 2 if arr[mid] < arr[left]: arr[left], arr[mid] = arr[mid], arr[left] if arr[right] < arr[left]: arr[left], arr[right] = arr[right], arr[left] if arr[right] < arr[mid]: arr[mid], arr[right] = arr[right], arr[mid] return mid def partition(arr, left, right): # 三数取中选pivot，并放到right位置 mid_idx = median_of_three(arr, left, right) arr[mid_idx], arr[right] = arr[right], arr[mid_idx] pivot = arr[right] i, j = left, right - 1 while True: while i <= j and arr[i] < pivot: i += 1 while i <= j and arr[j] > pivot: j -= 1 if i >= j: break arr[i], arr[j] = arr[j], arr[i] i += 1 j -= 1 arr[i], arr[right] = arr[right], arr[i] return i def quicksort(arr, left=0, right=None): if right is None: right = len(arr) - 1 # 小数组用插入排序 if right - left + 1 <= 10: insertion_sort(arr, left, right) return # 尾递归优化：先处理小的子区间，大的用循环 while left < right: pi = partition(arr, left, right) # 确保左区间不比右区间大，先递归小的，大的用循环处理 if pi - left < right - pi: quicksort(arr, left, pi - 1) left = pi + 1 else: quicksort(arr, pi + 1, right) right = pi - 1 ```

Python——你吃饭的筷子

全站热榜

创作者周榜