屏幕右上角的倒计时还剩三分钟，林晨做了个深呼吸。面前是T厂在线面试平台的代码编辑器界面，左侧是题目描述，要求手写快速排序算法，并分析时间复杂度。
上一轮王工的肯定还在耳边，但林晨清楚，二面才是真刀真枪。他活动了一下手指，目光扫过题目要求——不仅要写出来，还要解释优化点。
倒计时归零。
“林工，准备好了吗”？耳机里传来声音，比王工更沉稳些，带着一种技术人特有的冷静。
“准备好了”。林晨对着摄像头点点头。
“好，第一题，快速排序。给你十五分钟，写核心代码，然后讲思路”。面试官顿了顿，“提醒一下，我们关注边界条件、原地排序的实现，以及你在实际工程中如何应用或优化这个算法”。
林晨没有立刻敲代码。他盯着空白编辑器，脑海里先过了一遍流程：选基准、分区、递归。但面试官最后一句话是重点——实际工程应用。
他敲下第一行注释：“Python实现，原地排序，避免递归过深时栈溢出风险”。
手指在键盘上跳动，代码流畅地出现。他刻意避开了教科书上最简单的递归版本，而是采用了栈模拟递归的迭代写法，并在分区函数里加入了针对近乎有序数组的优化——随机选择基准元素。
def quick_sort_iterative(arr):
if not arr or len(arr) ＜= 1:
return arr
stack = [(0, len(arr)-1)]
while stack:
low, high = stack.pop
if low ＞= high:
continue
# 随机选择基准，避免近乎有序数组退化到O(n^2)
pivot_idx = random.randint(low, high)
arr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]
pivot = arr[low]
# 分区操作
i, j = low + 1, high
while i ＜= j:
while i ＜= j and arr[
（本章节未完结，点击下一页翻页继续阅读）
正在加载...