AI大模型面试硬核实战：双塔架构与业务链路技术闭环

写在前面

欢迎大家

Rocky Ding

《三年面试五年模拟》AIGC/LLM/AI Agent算法工程师/开发工程师求职面试秘籍独家资源：;
【三年面试五年模拟】WeThinkIn/AIGC-Interview-Book
，;欢迎大家Star～

Rocky最新撰写的10万字AI Agent（AI智能体）深入浅出全维度解析文章：;

深入浅出完整解析AI Agent（AI智能体）的核心基础知识

AIGC/LLM/AI Agent算法岗/开发岗求职面试内推学习社群
（涵盖AIGC、LLM大模型、AI Agent、传统深度学习、自动驾驶、机器学习、计算机视觉、自然语言处理、强化学习、大数据挖掘、具身智能、元宇宙、AGI等AI行业最新面试干货经验与核心知识）欢迎大家加入：;

大家好，;我是Rocky。

一、项目深挖

1. 介绍项目业务背景、完整业务链路，;线上Query、Item数据量级

回答：;

回答这道题不能只说“做了一个双塔模型”，;要把业务目标、数据对象、离线训练、在线召回/排序和指标闭环串起来。完整项目最终要解决的是：;在可接受的延迟和成本内，;把用户当前意图与合适的 Item 排在前面。

业务链路可以抽象为：;

Query/User

→

意图理解与特征构建

→

候选召回

→

精排/重排

→

过滤与规则

→

展示

→

行为日志回流

\text{Query/User} \rightarrow \text{意图理解与特征构建} \rightarrow \text{候选召回} \rightarrow \text{精排/重排} \rightarrow \text{过滤与规则} \rightarrow \text{展示} \rightarrow \text{行为日志回流}

Query/User

→

意图理解与特征构建

→

候选召回

→

精排

重排

→

过滤与规则

→

展示

→

行为日志回流

离线侧从曝光、点击、停留、收藏、评论、转化和负反馈日志中构造样本，;完成去重、脱敏、时间切分、负样本构造和特征加工；训练后将 Item 向量离线生成并写入 ANN 索引。在线收到 Query 后，;先做规范化、纠错、意图识别和 Query 编码，;再从向量索引、倒排索引或其他召回源取得候选，;之后由精排模型结合 Query、User、Item 和上下文特征打分，;最后做去重、质量过滤、业务规则和分页。

Query 与 Item 的量级要分别报告，;不要把训练样本数与线上实体数混为一谈。至少准备 Item 库规模、日新增 Item、日活跃 Query、训练样本量、线上 QPS/P99、初召候选数和最终展示数。敏感数字可以回答数量级，;但不能编造。

数据规模还要与设计决策对应：;Item 数量决定索引、分片和更新策略；Query 长尾决定纠错、改写和语义召回的重要性；QPS/P99 决定缓存、批量编码、量化和多级召回；Item 更新频率决定增量索引和一致性方案。项目介绍的本质不是报大数字，;而是说明规模如何约束模型与系统。

2. 说明测试集搭建方案，;AUC评估逻辑，;模型效果提升判定标准

回答：;

测试集要回答三个问题：;在什么分布上评估、标签是否可信、离线提升是否具有统计和业务意义。不能随机切一份数据就称为测试集。

我会优先按时间切分，;避免未来行为泄露；按 Query、User、Item 做去重或隔离，;防止近重复样本跨集合。测试样本覆盖头部、腰部、长尾 Query，;热门与冷启动 Item，;明确意图、歧义意图以及正反馈、弱反馈和无反馈。负样本不能只有随机负例，;还要有曝光未点击、同 Query 被跳过 Item 和模型易混淆的 hard negative，;并记录采样来源。

AUC 表示随机抽取一个正样本和一个负样本时，;模型把正样本打分更高的概率：;

AUC

⁡

(

)

(

−

)

\operatorname{AUC}=P\left(s(x^+)>s(x^-)\right)

AUC

(

)

(

−

)

AUC 本质上是排序概率，;不依赖固定阈值，;对分数的单调变换不敏感。但它不等于 Top-K 检索效果，;也不体现位置权重、召回覆盖和延迟。搜索还要看 Recall@K、MRR、nDCG、HitRate、无结果率、首屏命中；推荐还要结合 CTR、停留、转化、负反馈和长期价值。

效果提升不能只看 AUC 多了 0.001。应固定测试集、特征快照和评测脚本，;比较核心指标、分桶指标、坏例和置信区间，;必要时用 bootstrap 或配对检验。上线前做离线回放和 shadow，;线上通过随机分流 A/B 观察主指标、护栏指标、P99、成本和异常率。

没有线上实验时，;只能说“离线指标在预设阈值和多个分桶上稳定提升”，;不能把离线 AUC 直接等同于业务收益。

3. 阐述MSE收敛但排序效果下滑问题的发现、定位全过程

回答：;

MSE 收敛而排序效果下降，;首先说明训练目标与业务目标不一致，;或者训练/评估分布发生了变化。MSE 优化点值误差：;

∑

(

−

)

\mathcal{L}_{MSE}=\frac{1}{N}\sum_{i=1}^{N}(y_i-\hat y_i)^2

∑

(

−

)

它关注数值平均误差，;排序指标关注样本相对顺序。模型把大量预测压到均值附近，;可能让 MSE 下降，;却不能把真正相关的 Item 排在前面。标签噪声、类别不平衡、热门样本主导、曝光偏差、数据泄露、特征失效、分布漂移和推理预处理不一致也会产生类似现象。

定位分四层：;

检查 MSE、AUC、nDCG 的样本范围、权重、过滤和分桶，;确认没有把 Query 内排序错算成全局分类。

比较新旧模型分数方差、正负分布、校准曲线、分位数和 Query 内分数差距，;检查 score collapse、极端值或全同分。

找 Query 内正样本被负样本超过的逆序对，;分析语义、特征、hard negative、标签和索引问题，;同时检查训练/测试实体与时间重合。

对比训练、导出、量化和线上服务，;检查 tokenizer、池化、归一化、特征顺序、模型版本与 ANN metric。

修复不能只调学习率。可以把 MSE 与 BCE、pairwise loss 或 InfoNCE 联合，;让模型学习绝对相关性和相对区分性；重做 hard negative、曝光去偏和假负样本治理，;并对 Query 频段、Item 新鲜度和业务场景分桶评估。每项修改都做消融，;明确收益来自损失、数据、特征还是服务链路。

本质上，;训练 loss 只是优化代理，;排序指标和业务指标才是目标。loss 下降不能自动证明模型变好。

4. 改用BCE+InfoNCE联合损失的原因，;两项损失各自带来的效果增益

回答：;

BCE 和 InfoNCE 解决两个层面的问题。BCE 是点式目标，;判断一个 Query-Item 对本身的相关概率；InfoNCE 是对比目标，;让正样本在候选集合中排到负样本前面。

−

[

log

⁡

(

)

(

−

)

log

⁡

(

−

(

)

]

\mathcal{L}_{BCE} =-\left[y\log\sigma(z)+(1-y)\log(1-\sigma(z))\right]

−

[

lo
g

(

)

(

−

)

lo
g

(

−

(

))

]

−

log

⁡

exp

⁡

(

sim

⁡

(

)

∑

exp

⁡

(

sim

⁡

(

)

\mathcal{L}_{InfoNCE} =-\log \frac{\exp(\operatorname{sim}(q,i^+)/\tau)} {\sum_{j=1}^{K}\exp(\operatorname{sim}(q,i_j)/\tau)}

−

lo
g

∑

exp

(

sim

(

)

exp

(

sim

(

)

联合目标通常为：;

(

−

)

\mathcal{L} =\lambda\mathcal{L}_{BCE} +(1-\lambda)\mathcal{L}_{InfoNCE}

(

−

)

BCE 的增益通常体现在分数校准、绝对相关性判断和业务标签拟合；InfoNCE 通常改善 Embedding 空间分离、召回排序和长尾语义匹配。但没有消融实验不能声称某一项带来固定增益。应设置 BCE-only、InfoNCE-only、联合损失和不同

\lambda

的实验，;比较 AUC、Recall@K、nDCG、分桶和线上指标。

联合训练还要处理 loss 尺度不同、温度

\tau

、批内假负样本和点击偏差。真正的理由不是“多加一个 loss 更强”，;而是两种监督是否提供互补信号，;并且稳定性和成本是否可接受。

5. 基于原生NTP任务Qwen模型，;如何适配下游检索监督训练

回答：;

原生 NTP 训练的是条件语言建模能力，;不等于已经具备可直接用于向量检索的 Query-Item 表示。适配时可以复用 Qwen Transformer 主干，;在 Query 和 Item 两侧共享或部分共享参数，;取有效 token 的最后隐状态、特殊 pooling token 或 attention pooling，;再经过投影头得到向量：;

(

)

(

)

e_q=f_\theta(q),\qquad e_i=g_\theta(i)

(

)

(

)

训练构造正样本

(

)

(q,i^+)

(

)

和负样本

−

i^-

−

，;使用余弦/点积相似度配合 InfoNCE、Multiple Negatives Ranking Loss 或 pairwise loss。批内 Item 可作为负样本，;同时加入经过曝光约束和语义过滤的 hard negative。训练后 Query 与 Item 必须使用一致的 tokenizer、池化、归一化和向量库 metric；Item 向量离线入库，;Query 向量在线计算。

如果需要保留生成能力，;可以采用多任务目标：;

\mathcal{L} =\lambda_{NTP}\mathcal{L}_{NTP} +\lambda_{retrieval}\mathcal{L}_{retrieval}

交叉编码精排则把 Query 和 Item 拼接输入模型，;获得更充分的语义交互，;但无法提前计算所有 Item 向量，;在线成本更高。池化时不能取 padding 位置，;也不能忽略 attention mask；不同长度要按有效 token 做 masked mean 或使用明确 EOS 表示。

本质上，;这是把生成式语言表示迁移到可检索的度量空间，;同时用检索监督塑造“相似样本靠近、难负样本分离”的几何结构。

6. 检索打分选用余弦相似度，;不直接使用模型logits的理由

回答：;

生成模型 logits 和检索相似度不在同一语义空间。Qwen logits 通常是词表大小的向量：;

\mathbf{z}_t=W_oh_t+b

它表示上下文

h_t

下下一个 token 的条件分布，;受 prompt、位置、tokenizer、回答长度和词表影响。两个 Item 的词表 logits 不能天然作为稳定的 Query-Item 距离。

余弦相似度作用于经过同一表示学习目标训练的固定向量：;

cos

⁡

(

)

∥

\operatorname{cos}(q,i) =\frac{q^\mathsf{T}i}{\lVert q\rVert_2\lVert i\rVert_2}

cos

(

)

∥

它允许 Query 与 Item 独立编码，;Item 向量离线建立 ANN 索引；归一化后尺度更稳定，;固定维度也便于缓存、量化和分片。

如果用生成模型 logits 对每个候选 Item 判断相关性，;本质上是 Cross-Encoder：;需要把 Query 和 Item 一起送入模型，;精度可能更高，;但每个候选都要做昂贵前向，;不能承担大规模初召。常见分层方案是双塔向量初召，;Cross-Encoder 或 log-prob 精排。

余弦也不是天然正确，;必须确认 Query/Item 向量由匹配目标训练，;入库与查询使用一致的归一化和 metric，;并用 Recall@K、nDCG、延迟和线上指标验证。

7. vLLM FP16均值池化出现溢出、NaN问题的排查与修复方案

回答：;

先区分 hidden 在池化前已经 NaN，;还是池化归约阶段产生 NaN。FP16 最大有限值约为 65504，;长序列中先用半精度求和可能溢出，;即使最终平均值正常；有效 token 数为 0 或全 padding 则会产生 0/0。

排查顺序是：;

在模型输出、mask、pooling sum、除法、归一化和最终 embedding 后分别检查 isfinite、最大绝对值、有效长度和 dtype，;定位第一处非有限值。

核对 padding mask 语义、valid_count 和不同长度样本的统计；全 mask 行不能直接做 Softmax 或平均。

用 batch size 1、短序列和 eager 路径复现，;再与 vLLM fused kernel、量化/非量化路径对比，;检查导出模型、权重 dtype、KV Cache 和 pooling 接口。

如果 hidden 已异常，;继续查 attention logits、mask 中的 -inf、位置编码、权重加载、输入归一化和模型本身的数值范围。

修复时将 hidden、累加和归一化显式转为 FP32，;并保护分母：;

∑

max

⁡

(

∑

)

h=\frac{\sum_t m_t x_t}{\max\left(\sum_t m_t,1\right)}

max

(

∑

)

∑

具体做法是用有效 mask 做 FP32 sum，;除以 valid_count.clamp_min(1)，;再在 FP32 中做 L2 norm 和 normalize，;最后按向量库接口决定是否转回 FP16。全 padding 应返回错误、跳过或带状态的零向量，;不能默默当成正常 embedding。

BF16 指数范围更宽，;可能缓解溢出，;但不是不定位根因的万能修复；随意 clamp 也可能掩盖模型异常。修复后要回归空输入、超长输入、全 padding、极端值、不同 batch 和真实请求，;检查 NaN 率、向量范数、召回和吞吐。

二、理论八股

1. 搜索、推荐任务在建模逻辑、标签设计上的核心差异

回答：;

搜索是 Query 驱动的需求满足，;推荐是 User/场景驱动的内容发现。

维度搜索推荐触发方式用户主动输入 Query，;意图通常更明确系统主动提供内容，;意图隐式核心目标Query-Item 相关性、满足度、结果完整性长期兴趣、消费深度、留存与多样性标签Query-Item 点击、停留、收藏、转化、人工相关性曝光后的点击、观看时长、完播、互动、留存、负反馈样本偏差位置、召回源、Query 改写和无结果偏差曝光策略、位置偏差、反馈回流和热门偏差指标Recall@K、MRR、nDCG、无结果率、首屏命中CTR、观看时长、完播率、转化、留存、多样性

搜索强调“这个 Item 是否回答当前 Query”，;要建模 Query-Item 交互、实体、时间和过滤条件；推荐除了相关性，;还要建模兴趣、曝光频率、新鲜度、探索利用和生态约束。搜索可以满足明确需求，;推荐则要探索用户尚未表达的偏好。

点击不能直接当成无偏真相关。搜索点击受位置、标题和摘要影响，;推荐点击受封面、曝光策略和疲劳影响；应结合停留、跳过、负反馈、转化、人工标注和反事实校正。两者可共享底层表示和基础设施，;但训练目标、采样、指标和线上策略不能简单视为同一问题。

2. 搜索场景Query独有特性，;User-Query-Item三者建模方案

回答：;

搜索 Query 通常比推荐场景信号更短，;但信息密度更高。一个 Query 可能同时包含实体、属性、时间、地点、价格、排序偏好和过滤条件，;也可能存在错别字、口语表达、歧义、新词和极长尾。它表达的是用户此刻的显式任务，;不一定等于用户的长期兴趣。

建模上可以拆成三层：;

Query-Item 相关性。
用 Query Encoder 和 Item Encoder 生成向量做双塔召回，;同时保留倒排、规则和结构化过滤，;覆盖精确词匹配、实体约束与语义匹配。

User-Query 意图关系。
从用户近期搜索、点击、收藏、停留和跳过行为提取短期序列，;判断当前 Query 与历史兴趣是否一致，;必要时做 Query 改写、意图分类和个性化召回。

User-Query-Item 交互精排。
在候选规模可控后，;将用户画像、Query 解析结果、Item 内容、交叉特征和上下文一起输入 Cross-Encoder 或排序模型。

可以用一个概念化的分解表示最终分数：;

(

)

(

)

s(u,q,i)=s_{q,i}+s_{u,q}+s_{u,i}+\phi(u,q,i)

(

)

(

)

其中

s_{q,i}

是显式相关性，;

s_{u,q}

是用户与当前意图的关系，;

s_{u,i}

是用户长期偏好，;

\phi

表示三者交叉特征。线上策略不能让长期偏好覆盖 Query 的明确约束。例如用户长期喜欢美食内容，;但搜索“北京朝阳区今天的羽毛球馆”，;地点、时间和实体约束应优先满足。

工程上还要把 Query 的硬约束与软偏好分开：;硬约束进入过滤或高权重特征，;软偏好进入排序；对新词、冷启动和无历史用户保留倒排、热门、内容质量和语义兜底。最终用分 Query 类型的 Recall@K、nDCG、无结果率和线上满意度验证，;而不是只看整体平均指标。

3. 选择LoRA微调而非全量微调的原因

回答：;

LoRA 的核心是冻结预训练权重，;只训练低秩增量：;

W=W_0+\Delta W=W_0+\frac{\alpha}{r}BA

其中

W_0

是底座权重，;

∈

A\in\mathbb{R}^{r\times d_{in}}

∈

、

∈

B\in\mathbb{R}^{d_{out}\times r}

∈

，;且

远小于原矩阵维度。这样优化器只维护 Adapter 参数和状态，;不需要为全部参数保存梯度与优化器状态。

选择 LoRA 的主要理由是显存和训练成本更低、迭代速度快、便于为不同业务保存多个 Adapter、底座模型可复用，;且在任务规模适中时通常能达到接近全量微调的效果。对于检索监督训练，;还可以只在 attention、MLP 等敏感模块挂载 Adapter，;快速做 rank、目标层和损失的消融。

但不能说 LoRA 永远优于全量微调。全量微调的参数容量更大，;适合数据量充分、领域与底座差异大、需要重构知识或行为分布的任务；它也更容易达到任务上限，;但显存、通信、训练时间、灾难性遗忘和版本管理成本更高。LoRA 可能受低秩容量限制，;也可能把底座的错误偏差保留下来。

面试时应明确决策依据：;先用 LoRA 验证数据和目标是否有效，;再根据验证集、长尾分桶、泛化、吞吐、成本和线上收益决定是否扩大 rank、使用 QLoRA、多个 Adapter，;或进入全量微调。

4. LoRA底层原理、Rank选取依据、A/B矩阵初始化细节

回答：;

LoRA 将权重更新约束在低秩子空间：;

\Delta W=\frac{\alpha}{r}BA

前向时可以把

W_0x

与

BAx

相加，;训练时冻结

W_0

，;只更新

和

。

决定可表达的更新秩：;增大

会提高适配容量，;但增加参数量、显存、通信和过拟合风险；减小

成本低，;但可能无法表达任务所需的变化。

Rank 不应凭经验固定。应在固定数据切分和训练预算下做小规模网格实验，;并按模块、层深和任务类型观察验证集指标、长尾效果、稳定性与推理成本。可以先用较小 rank 快速筛选，;再对敏感层增大 rank；不要只根据训练 loss 选择，;因为更大的 rank 可能只是记住噪声。

常见初始化是

随机初始化、

全零初始化，;因此初始时：;

\Delta W_0=B_0A_0=0

模型一开始等价于底座模型，;训练过程再逐渐引入任务更新。不能让

、

同时为零，;否则两者的梯度会同时失去有效更新信号。缩放因子

\alpha/r

用于控制增量幅度；LoRA dropout 可以降低过拟合，;目标模块决定适配能力和成本，;量化底座时要注意反量化计算、累加精度以及是否在合并权重时使用 FP32。

部署时可以保留 Adapter 动态加载，;也可以把

合并回权重以减少额外算子。合并应校验 dtype、量化误差和多 Adapter 兼容性；训练、导出和线上推理的 tokenizer、池化、归一化也必须保持一致。

5. InfoNCE假负样本带来的负面影响，;对应的缓解手段

回答：;

InfoNCE 通常把同一 batch 中其他 Item 当作负样本：;

−

log

⁡

exp

⁡

(

)

∑

exp

⁡

(

)

\mathcal{L}_i=-\log\frac{\exp(s(q_i,i_i^+)/\tau)}{\sum_j\exp(s(q_i,i_j)/\tau)}

−

lo
g

∑

exp

(

)

exp

(

)

但同一个 Item 可能同时满足多个 Query，;或 batch 中存在语义相近、业务上也相关的 Item。把它们强行当负样本就是假负样本，;会错误地把真实相关内容推远，;破坏 embedding 空间，;尤其伤害多兴趣、长尾、同主题、多正样本和 Recall@K。

我会先按样本 ID、内容实体、Query 意图和时间窗口做去重，;再使用曝光、点击、收藏、人工相关性或教师模型构造负样本 mask。一个 Query 有多个正例时用 multi-positive InfoNCE，;让多个正例进入分子或正例集合，;而不是只保留一个对角线正例。对高度相似但标签不确定的样本可以降权、忽略或单独作为软负例。

此外可以做分层负采样：;随机负例提供覆盖，;模型高分但明确不相关的 hard negative 提供区分能力，;潜在正例则屏蔽；用 cross-encoder、规则和人工抽检识别假负样本。更复杂的场景可使用 debiased contrastive learning 或教师分布蒸馏，;但核心仍是降低错误监督。

不能为了消除假负样本而删除所有 hard negative，;否则模型会失去边界学习。应通过消融比较负样本策略对 Recall@K、nDCG、长尾分桶、训练稳定性和线上负反馈的影响。

6. 写出BCE损失公式，;分析软标签能否直接参与训练

回答：;

二分类交叉熵为：;

−

[

log

⁡

(

−

)

log

⁡

(

−

)

]

\mathcal{L}_{BCE}=-\left[y\log p+(1-y)\log(1-p)\right]

−

[

lo
g

(

−

)

lo
g

(

−

)

]

其中

∈

{

}

y\in\{0,1\}

∈

{

}

是标签，;

(

)

p=\sigma(z)

(

)

是正类概率。工程实现优先使用
BCEWithLogitsLoss
，;把 sigmoid 和 BCE 合并计算，;避免概率接近 0 或 1 时的数值不稳定。

软标签

∈

[

]

y\in[0,1]

∈

[

]

可以直接参与 BCE，;因为公式本身只要求目标落在概率区间内；它可以表达教师模型置信度、人工标注的平均意见或由点击/停留/转化融合出的相关概率。但“能计算”不等于“语义正确”：;软标签必须有概率或期望意义，;不能把任意分数未经校准地塞进去。

例如教师分数应先做温度校准、Platt scaling 或分桶校准；不同数据源的标签尺度要统一。样本权重
weight
表示该样本对目标的可信度或重要程度，;不能误当成软标签。还要处理类别不平衡、曝光偏差、标签泄露和同一 Query 内的相对排序需求，;必要时引入
pos_weight
、sample weight、pairwise loss 或 InfoNCE。

软标签的收益要通过硬标签和软标签对照、校准误差、AUC/nDCG、分桶效果及线上实验验证。若软标签只是把噪声平滑了，;可能降低梯度尖锐度，;却不一定提升排序。

7. 手写InfoNCE矩阵表达式，;讲解代码实现思路

回答：;

设一个 batch 有

对 Query-Item，;经过编码并归一化得到：;

∈

Q,K\in\mathbb{R}^{B\times d},\qquad S=\frac{QK^\mathsf{T}}{\tau}\in\mathbb{R}^{B\times B}

∈

矩阵

S_{ij}

是第

个 Query 与第

个 Item 的相似度，;第

行的正确标签是

，;因此行方向的交叉熵就是 Query-to-Item InfoNCE：;

→

⁡

(

[

…

−

]

)

\mathcal{L}_{q\rightarrow i}=\operatorname{CE}(S, [0,1,\ldots,B-1])

→

(

[

…

−

])

代码实现的关键步骤是
F.normalize
得到单位向量，;矩阵乘法得到全部配对分数，;除以温度
tau
，;直接把对角线索引作为
cross_entropy
的 target。不要先手动 Softmax，;因为交叉熵内部会做稳定的
log_softmax
。

import torch
import torch.nn.functional as F

q = F.normalize(query_emb, dim=-1)
k = F.normalize(item_emb, dim=-1)
logits = q @ k.transpose(0, 1) / tau
labels = torch.arange(logits.size(0), device=logits.device)
loss_qi = F.cross_entropy(logits, labels)
loss = loss_qi

如果 Query-to-Item 和 Item-to-Query 都重要，;可以计算转置矩阵上的对称损失并取平均。分布式训练时用
all_gather
收集其他卡的 Item 向量扩大负样本池，;但必须处理梯度策略、全局样本 ID 对齐、重复样本和跨卡假负样本。多正例任务要用正例 mask 改写分母/分子，;而不是机械地把对角线当成唯一正例。

温度越小，;分布越尖锐，;区分能力和梯度都更强，;但对噪声、假负样本和数值稳定性更敏感；温度与 batch size、向量归一化和负样本质量应联合调参。

三、代码手撕

1. 现场编写快速排序算法，;讲解实现思路

回答：;

我会采用三路快排，;把数组划分为“小于 pivot、等于 pivot、大于 pivot”三段。三路划分对重复值很多的输入更稳健，;且在遇到大于 pivot 的元素时，;换回来的元素还没有检查，;所以
cur
不能立即增加。

def quick_sort(nums):
    def sort(left, right):
        if left >= right:
            return

        pivot = nums[(left + right) // 2]
        lt, cur, gt = left, left, right

        while cur <= gt:
            if nums[cur] < pivot:
                nums[lt], nums[cur] = nums[cur], nums[lt]
                lt += 1
                cur += 1
            elif nums[cur] > pivot:
                nums[cur], nums[gt] = nums[gt], nums[cur]
                gt -= 1
            else:
                cur += 1

        sort(left, lt - 1)
        sort(gt + 1, right)

    sort(0, len(nums) - 1)
    return nums

循环结束时，;
[left, lt)
小于 pivot，;
[lt, gt]
等于 pivot，;
(gt, right]
大于 pivot，;再递归处理两侧。平均时间复杂度是

(

log

⁡

)

O(n\log n)

(

lo
g

)

，;最坏为

(

)

O(n^2)

(

)

；平均递归栈为

(

log

⁡

)

O(\log n)

(

lo
g

)

，;最坏为

(

)

O(n)

(

)

，;这里是在原数组上原地排序，;额外空间主要来自递归栈。

需要测试空数组、单元素、已排序、逆序、全相同、重复值、负数和极端长度。生产代码还可以用随机 pivot、较小区间切换插入排序、尾递归消除或显式栈降低最坏栈深；如果必须保证最坏时间复杂度，;则应考虑堆排序或 introsort。

AI大模型面试硬核实战：双塔架构与业务链路技术闭环

猜你喜欢

评论0