一一中文网

手机浏览器扫描二维码访问

第97章 算法面（第1页）

屏幕右上角的倒计时还剩三分钟，林晨做了个深呼吸。

面前是t厂在线面试平台的代码编辑器界面，左侧是题目描述，要求手写快速排序算法，并分析时间复杂度。

上一轮王工的肯定还在耳边，但林晨清楚，二面才是真刀真枪。

他活动了一下手指，目光扫过题目要求——不仅要写出来，还要解释优化点。

倒计时归零。

“林工，准备好了吗”

？耳机里传来声音，比王工更沉稳些，带着一种技术人特有的冷静。

“准备好了”

。

林晨对着摄像头点点头。

“好，第一题，快速排序。

给你十五分钟，写核心代码，然后讲思路”

。

面试官顿了顿，“提醒一下，我们关注边界条件、原地排序的实现，以及你在实际工程中如何应用或优化这个算法”

。

林晨没有立刻敲代码。

他盯着空白编辑器，脑海里先过了一遍流程：选基准、分区、递归。

但面试官最后一句话是重点——实际工程应用。

他敲下第一行注释：“python实现，原地排序，避免递归过深时栈溢出风险”

。

手指在键盘上跳动，代码流畅地出现。

他刻意避开了教科书上最简单的递归版本，而是采用了栈模拟递归的迭代写法，并在分区函数里加入了针对近乎有序数组的优化——随机选择基准元素。

defquick_sort_iterative（arr）:

ifnotarrorlen（arr）＜=1:

returnarr

stack=[（0，len（arr）-1）]

whilestack:

low，high=stack.pop

iflow＞=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

whilei＜=j: