一一中文网

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

第97章 算法面（第2页）

whilei＜=jandarr[i]＜=pivot:

i+=1

whilei＜=jandarr[j]＞pivot:

j-=1

ifi＜j:

arr[i]，arr[j]=arr[j]，arr[i]

arr[low]，arr[j]=arr[j]，arr[low]

#先压入较大的区间，控制栈深度

if（j-low）＞（high-j）:

stack.append（（low，j-1））

stack.append（（j+1，high））

else:

stack.append（（j+1，high））

stack.append（（low，j-1））

returnarr

写完代码，时间才过去八分钟。

“我写完了”

。

林晨说。

“比预期快”

。

面试官的声音听不出情绪，“先解释一下为什么用迭代而不是递归”

？

“两个考虑”

。

林晨清了清嗓子，“第一，工程实践中，递归深度受系统栈限制，处理大规模数据有风险。

第二，迭代版本更容易加入自定义的调度策略——比如我刚才优先处理较小分区，这能进一步控制栈的使用量”

。

“随机选择基准呢”

？

“这是应对实际数据分布的策略。

教科书上的快速排序在最坏情况下——比如数组已经有序或逆序——会退化到o（n2）。

真实业务数据常常有部分有序的特征，随机化能保证数学期望上的o（nlogn），更稳定”

。

面试官沉默了几秒，林晨能听到那头轻微的键盘敲击声，大概是在记录。

“时间复杂度分析”

。