一、排序算法概述：从搜索的本质说起
大家好，我是这门课的主讲人。今天咱们聊聊排序算法——这个看似基础、实则贯穿整个搜索系统的核心话题。
说实话，我刚入行那会儿，觉得排序不就是把一堆东西排个序嘛，有什么好讲的？直到我在一个电商搜索项目中栽了跟头——用户搜"手机"，结果第一页全是几十块的老人机，用户直接骂娘。嗯，从那以后我才真正明白：排序算法，决定了用户看到什么，也决定了搜索系统的生死。
什么是排序算法？
排序算法，说白了就是给一堆杂乱无章的东西排个先后顺序。在搜索场景里，就是决定哪些结果排在前面，哪些排在后面。
你想想看，用户搜一个关键词，系统可能召回了几万条结果。但用户只看得见前10条、前20条。这时候，排序算法就是那个"裁判"——它决定谁能站上领奖台。
我个人习惯把排序算法分成两类：
- 传统排序：比如冒泡、快排、归并——这些是"怎么排"的问题
- 搜索排序：比如BM25、Learning to Rank——这些是"按什么标准排"的问题
咱们这门课，重点讲的是后者。但别急，前者的一些思想也会穿插进来。
排序算法在搜索中的重要性
我见过太多团队，花大把精力搞召回、搞索引，最后排序随便写个公式就上线了。结果呢？用户留存率惨不忍睹。
为什么排序这么重要？我给你三个理由：
- 用户只看前几条——研究表明，超过70%的用户不会翻到第二页。排在前面的结果，直接决定了用户对搜索系统的第一印象。
- 排序影响转化率——我在做电商搜索时发现，把高转化商品排到前三，整体GMV能提升15%以上。这不是玄学，是实打实的数据。
- 排序体现"理解"——好的排序算法，能理解用户意图。比如搜"苹果"，有人想要水果，有人想要手机。排序算法得能区分这些。
核心观点：搜索系统里，召回决定了"有没有"，排序决定了"好不好"。没有好的排序，再牛的召回也是白搭。
评价指标：怎么衡量排序好不好？
聊完重要性，咱们得说说怎么评价排序效果。我踩过的坑太多了——曾经有个项目，上线前看指标一片大好，上线后用户反馈一塌糊涂。为什么？因为指标选错了。
下面这几个指标，是我个人认为最常用的，也是面试必问的：
1. 准确率（Precision）
准确率，就是"你排上去的结果里，有多少是相关的"。
公式很简单：
Precision = 相关的结果数 / 返回的结果总数举个例子：你返回了10条结果，其中7条是用户想要的。那准确率就是70%。
但要注意——准确率有个坑。我曾经在一个项目中只追求准确率，结果排上去的都是最保守、最安全的结果，用户觉得"搜来搜去就那几样"。说白了，准确率高了，但多样性没了。
2. 召回率（Recall）
召回率，就是"所有相关的结果里，你找回来了多少"。
Recall = 相关的结果数 / 系统中所有相关的结果总数还是那个例子：系统里有100条相关结果，你只返回了7条。那召回率就是7%。
你可能会问：那是不是召回率越高越好？不一定。我见过有人为了追求召回率，把一堆不相关的结果也塞进来，结果准确率暴跌。准确率和召回率，就像跷跷板的两头——你压下去一个，另一个就翘起来。
我的经验：实际项目中，我们通常用F1-score来平衡两者。F1 = 2 * (Precision * Recall) / (Precision + Recall)。这个值越高，说明整体效果越好。
3. NDCG（归一化折损累计增益）
这个指标，我得说——它是排序评价的"王牌"。为什么？因为它不仅关心结果是否相关，还关心相关的结果排在了哪里。
NDCG的核心思想很简单：
- 相关的结果，排得越靠前越好
- 排在前面的结果，权重更高
- 排在后面对用户影响小，权重就低
计算公式分三步：
1. CG（累计增益）：把所有结果的相关性得分加起来
CG = rel1 + rel2 + ... + reln
2. DCG（折损累计增益）：位置越靠后，折损越大
DCG = rel1 + rel2/log2(2) + rel3/log2(3) + ... + reln/log2(n)
3. NDCG：用DCG除以理想情况下的IDCG
NDCG = DCG / IDCG举个例子你就明白了：
| 位置 | 结果A（相关性分） | 结果B（相关性分） |
|---|---|---|
| 1 | 3（非常相关） | 1（不太相关） |
| 2 | 1 | 3 |
| 3 | 2 | 2 |
结果A的DCG = 3 + 1/log2(2) + 2/log2(3) ≈ 3 + 1 + 1.26 = 5.26
结果B的DCG = 1 + 3/log2(2) + 2/log2(3) ≈ 1 + 3 + 1.26 = 5.26
你看，DCG值一样。但直觉告诉我们，结果A更好——因为最相关的结果排在了第一位。这时候NDCG就派上用场了：
理想排序应该是 [3, 2, 1]，IDCG = 3 + 2/log2(2) + 1/log2(3) ≈ 3 + 2 + 0.63 = 5.63
结果A的NDCG = 5.26 / 5.63 ≈ 0.93
结果B的NDCG = 5.26 / 5.63 ≈ 0.93
嗯？还是一样？别急，这是因为例子太简单了。实际场景中，相关性分数差异更大，NDCG能很好地反映排序质量。
避坑指南：我曾经在一个项目中直接用DCG做评估，结果发现不同查询的DCG值差异巨大，根本没法横向比较。后来改用NDCG，才解决了这个问题。记住：一定要用归一化后的版本。
4. MAP（平均准确率均值）
MAP，全称是Mean Average Precision。它衡量的是在所有相关结果的位置上，准确率的平均值。
怎么算？分两步：
- 对每个查询，计算AP（Average Precision）
- 对所有查询的AP取平均，得到MAP
AP的计算公式：
AP = (1/相关结果总数) * Σ(每个相关结果位置的准确率)举个例子：假设有3个相关结果，排在第1、第3、第5位。
- 第1位：准确率 = 1/1 = 1.0
- 第3位：准确率 = 2/3 ≈ 0.67
- 第5位：准确率 = 3/5 = 0.6
AP = (1.0 + 0.67 + 0.6) / 3 ≈ 0.76
MAP就是所有查询的AP的平均值。
MAP和NDCG的区别在哪？我个人的理解是：
- MAP更关注"相关结果有没有被排上来"
- NDCG更关注"相关结果排得够不够靠前"
实际项目中，我通常两个都看。如果MAP高但NDCG低，说明相关结果都找回来了，但排得不够靠前。如果NDCG高但MAP低，说明排在前面的结果很相关，但漏掉了一些相关结果。
小结
好了，这一章的内容就到这里。咱们聊了：
- 排序算法是什么——说白了就是"排座次"
- 排序为什么重要——它决定了用户看到什么
- 四个核心指标——准确率、召回率、NDCG、MAP
下一章，咱们会深入讲传统排序算法，包括冒泡、快排、归并这些经典算法。别觉得它们过时了——很多搜索系统的底层，用的就是这些思想。
最后说一句：评价指标选对了，你的排序系统就成功了一半。我见过太多人一上来就调模型、调参数，结果连指标都没搞清楚。嗯，希望你不是这样的人。