排序系列终篇：把前面各篇的算法放到一个选型框架里，帮助你在真实项目里快速决定“用什么排序、为何如此、如何验证”。

目标读者

• 需要在项目/面试/分享中快速给出排序选型理由的工程师。
• 想要一张实战速查表，结合规模、分布、稳定性与内存做决策的人。

背景/动机

• 排序算法众多，若缺少统一决策框架，容易“默认快排”或“盲目稳定”。
• 本文给出可执行的选型表 + 测试清单，覆盖内置排序、非比较、外部排序和混合策略。

A — Algorithm（主题与速查）

核心问题：在不同约束下选择合适的排序策略。

速查表（建议优先级）

• 稳定 + 近乎有序：TimSort / 归并（Python/Java 默认）。
• 原地 + 最坏有界：Introsort（C++ std::sort 思想）/ 堆排序。
• 范围/位数可知：计数/桶/基数排序。
• 小规模/近乎有序：插入排序；可作混合排序子过程。
• 外部排序（超内存）：分块 + 多路归并（稳定）。
• 演示/教学：冒泡/选择/插入对比稳定性与交换成本。

C — Concepts（核心维度）

E — Engineering（工程应用场景）

场景 1：接口分页排序（Go）

• 需求：中等规模、无稳定性要求、内存紧。
• 选型：标准库 sort.Slice（Introsort 思路），小段插排。
• 验证：构造逆序/重复多，确保无退化；统计耗时。

场景 2：日志批处理（Python）

• 需求：稳定、近乎有序（按时间分桶后拼接）。
• 选型：内置排序（TimSort）。
• 验证：构造局部逆序，检查稳定性保持相对顺序。

场景 3：大文件排序（C++）

• 需求：数据超内存，需稳定。
• 选型：外部排序（分块排序 + k 路归并）。
• 验证：控制块大小，测 I/O；用最小堆归并，确保稳定合并。

场景 4：范围已知的批量整数（Go）

• 需求：范围小，追求速度。
• 选型：计数排序或基数排序；范围大但位数有限用基数。
• 验证：估算 k 与 n；压力测试范围极值。

场景 5：前端表格稳定排序（JavaScript）

• 需求：稳定按多列排序。
• 选型：浏览器内置（多数稳定）或自定义稳定归并/TimSort；如不确定，映射索引保持稳定。

R — Reflection（反思与深入）

• 时间/空间权衡：原地但不稳定（快排/堆/Introsort） vs 稳定但需空间（归并/TimSort/计数/基数）。
• 最坏保证：需上界时选 Introsort/堆/归并；快排需防退化；TimSort 在最坏仍 O(n log n)。
• 数据特性：范围/位数可知时非比较排序优势巨大；近乎有序时 TimSort/插排有高性价比。
• 外部排序：I/O 主导，重点在分块大小、归并路数与临时文件管理。

S — Summary（总结）

• 选型先问四件事：规模/分布？稳定性？内存/外存？范围/位数？
• 内置排序通常足够：Python/Java（稳定 TimSort），C++/Go（Introsort 风格不稳定）；特殊需求再自定义。
• 非比较排序在范围/位数受限时是降复杂度的利器；外部排序用于超内存数据。
• 混合策略是工程常态：小段插排，深度回退堆排，run 检测与归并。

实践指南 / 步骤

• 写选型表：记录场景→需求→选择→理由。
• 基准测试：随机、逆序、近乎有序、重复多、范围受限、超内存六类数据。
• 加入监控：排序耗时、比较次数（如可测）、内存占用；外部排序测 I/O。
• 在 PR 模板或设计文档中填写“排序算法及理由”。

常见问题与注意事项

• 忽略稳定性：排序后业务依赖相对顺序时，须用稳定算法或索引映射。
• 低估内存：计数/基数在范围大时可能爆内存；外部排序需规划临时存储。
• 枢轴退化：自实现快排需随机/三数取中 + 小段插排 + 尾递归优化。
• 近乎有序却用快排：TimSort/插排可能更快。

可运行示例：简单选型函数（Python）

def choose_sort(stable: bool, n: int, range_known=False, near_sorted=False):
    if range_known:
        return "counting/radix" if stable else "counting/radix"
    if stable:
        if n > 5e5: return "merge/timsort"
        return "timsort"
    if near_sorted and n < 1e4:
        return "insertion"
    if n > 1e6:
        return "introsort/heap"
    return "introsort/quicksort"

print(choose_sort(stable=True, n=10000, range_known=False, near_sorted=True))

参考与延伸阅读

• 本系列前 7 篇：O(n²) 基线、希尔、归并、快排、堆、非比较、TimSort/Introsort。
• CLRS《算法导论》排序章节；Bentley & McIlroy 《Engineering a Sort Function》。

元信息

• 阅读时长：约 12 分钟
• SEO 关键词：排序选型, 稳定排序, 外部排序, TimSort, Introsort
• 元描述：排序专题终篇，给出按规模/分布/稳定性/内存的排序选型清单与测试指南，助你在工程中快速决策。

行动号召（CTA）

• 根据你的项目填写一张“排序选型表”，含场景/需求/算法/理由。
• 用真实数据跑基准测试六类分布，记录耗时与内存，验证选型。
• 若有外部排序需求，先做分块 + 归并的 PoC，评估 I/O 与存储成本。