排序算法及不同场景应用总结

排序算法及不同场景应用总结

一、常见排序算法分类与特性

1.1 基础比较类排序

• 冒泡排序：平均/最坏时间复杂度O(n2)O(n^2)O(n2)，最好O(n)O(n)O(n)，原地排序，稳定。
• 选择排序：全场景O(n2)O(n^2)O(n2)，原地排序，不稳定。
• 插入排序：平均/最坏O(n2)O(n^2)O(n2)，最好O(n)O(n)O(n)，原地排序，稳定，适用于小规模、基本有序数据。

1.2 进阶高效比较类排序

• 希尔排序：时间复杂度约O(n1.3)∼O(n2)O(n^{1.3}) \sim O(n^2)O(n1.3)∼O(n2)，原地排序，不稳定，分组插入实现。
• 归并排序：全场景O(nlog⁡n)O(n\log n)O(nlogn)，空间复杂度O(n)O(n)O(n)，稳定，基于分治思想，适合大数据、外排序场景。
• 快速排序：平均O(nlog⁡n)O(n\log n)O(nlogn)，最坏O(n2)O(n^2)O(n2)，空间O(log⁡n)O(\log n)O(logn)，不稳定，工程常用，综合性能优。
• 堆排序：全场景O(nlog⁡n)O(n\log n)O(nlogn)，原地排序，不稳定，常用于Top-K极值场景。

1.3 非比较类线性排序

• 计数排序：时间复杂度O(n+k)O(n+k)O(n+k)，空间O(n+k)O(n+k)O(n+k)，稳定，要求数据取值范围有限。
• 基数排序：时间复杂度O(d(n+k))O(d(n+k))O(d(n+k))，稳定，适用于整数、定长字符串。
• 桶排序：平均O(n)O(n)O(n)，最坏O(n2)O(n^2)O(n2)，稳定，依赖数据均匀分布。

二、数据库排序实现方案

2.1 索引优先策略

• 若ORDER BY字段存在有效索引，依托B+树索引天然有序特性，无需额外排序，性能最优。

2.2 文件排序（filesort）

2.2.1 内存排序

• 数据量小于排序缓冲区时，MySQL、SQL Server 采用快速排序；PostgreSQL、Oracle 结合快排/归并排序。

2.2.2 外部排序

• 数据超出内存限制，使用外部归并排序，分块排序后多路合并，适配海量磁盘数据。

2.2.3 Top-N 限定排序

• ORDER BY + LIMIT场景，采用堆排序，仅维护指定大小堆，降低计算开销。

三、搜索引擎排序架构与算法

3.1 整体流程

• 整体链路：召回 → 粗排 → 精排 → 重排，不做全量数据排序。

3.2 各阶段核心算法

3.2.1 召回阶段

• 依托倒排索引完成文档初筛选，搭配****堆排序（TopK）****截取高相关文档。
• 基础相关性打分：主流使用BM25，传统方案为 TF-IDF。

3.2.2 粗排阶段

• 采用轻量级模型（逻辑回归、双塔DNN），结合快速排序/堆排序缩减数据量级。
• 融合特征：相关性分数、PageRank、标题匹配度、时效性等。

3.2.3 精排阶段

• 工业主流：LambdaMART（LTR排序学习），基于GBDT优化排序指标。
• 进阶方案：DeepFM、DIN、BERT等深度模型，挖掘语义与个性化特征。

3.2.4 重排阶段

• 采用启发式规则、贪心算法，完成去重、多样性优化、业务规则适配。

3.3 经典辅助算法

• PageRank：衡量网页权威性，现为精排重要特征之一。

四、场景选型总结

• 小规模有序数据：优先插入排序。
• 通用内存排序：优先快速排序。
• 海量磁盘数据/要求稳定：优先归并排序。
• 求取Top-K极值：优先堆排序。
• 数值范围有限数据：优先计数/基数排序。
• 数据库：优先利用索引，根据内存、数据量自动切换快排、归并、堆排。
• 搜索引擎：倒排索引+堆排召回，多模型分层排序结合机器学习完成最终定序。