面向准备系统性写排序系列文章的读者：本文是序章，先用 ACERS 框架搭好“选型地图”，帮你快速判断何时用快排、归并、堆、计数/基数，以及 TimSort、Introsort 等工程实现。

目标读者

• 刷题进阶者：想写排序专题但需要整体结构。
• 后端/数据工程师：关心内存占用、稳定性与并发场景的排序选型。
• 教学/团队分享者：需要一套可复用的讲解框架和示例代码。

背景与动机

• 痛点：排序算法多且名字相似，容易混淆稳定性/复杂度，工程上还要考虑缓存友好度、外部排序和语言内置实现。
• 目标：给出一份“排序选型速查表 + 场景示例 + 代码骨架”，让后续系列文章有统一的结构和口径。

A — Algorithm（题目与算法）

主题：如何为不同输入规模、数据分布和稳定性需求选择合适的排序算法。

基础示例

• 示例 1：小数组（≤ 30）且基本有序 → 直接插入排序，开销小。
• 示例 2：中等规模随机数组（10⁴） → 快速排序或 Introsort。
• 示例 3：超大整数键且范围窄（10⁶ 以内） → 计数排序/桶排序。

简单输入输出

输入：n 个可比较元素的数组/切片
输出：按非降序排列的数组/切片

C — Concepts（核心思想）

归类

• 分治类：归并、快速。
• 基于堆：堆排序。
• 基于增量：希尔。
• 非比较类：计数、桶、基数。
• 工程混合：TimSort（插入 + 归并），Introsort（快排 + 堆排 + 插入）。

E — Engineering（工程应用）

场景 1：数据分析批处理（Python）

背景：处理 1e6 行日志，字段为字符串 + 时间戳，需要稳定排序保持同时间戳内原顺序。 为何适用：Python 内置排序是 TimSort，稳定且对局部有序数据表现好。

from operator import itemgetter

logs = [
    ("2025-11-01T10:00:00", "user1", 3),
    ("2025-11-01T10:00:00", "user2", 1),
    ("2025-11-01T10:00:01", "user3", 2),
]

# 按时间戳升序，稳定保持同时间戳的原顺序
logs.sort(key=itemgetter(0))
print(logs)

场景 2：后端服务分页排序（Go）

背景：接口需要对商品按价格升序、销量降序排序，数据量中等（< 1e5）。 为何适用：sort.Slice 原地、比较灵活；数据量适中，用快排/堆排混合的标准库足够。

package main

import (
    "fmt"
    "sort"
)

type Item struct { Price int; Sales int }

func main() {
    items := []Item{{100, 50}, {80, 200}, {100, 120}}
    sort.Slice(items, func(i, j int) bool {
        if items[i].Price == items[j].Price {
            return items[i].Sales > items[j].Sales // 销量降序
        }
        return items[i].Price < items[j].Price
    })
    fmt.Println(items)
}

场景 3：内存受限的离线排序（C++，外部归并）

背景：要对 10GB 的整数文件排序，内存仅 512MB。 为何适用：外部排序场景，使用分块写临时文件 + 归并，稳定且内存可控。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> buf;
    buf.reserve(1 << 20); // ~1M ints
    vector<string> tmpFiles;
    int x; int chunk = 0;
    while (cin >> x) {
        buf.push_back(x);
        if (buf.size() == buf.capacity()) {
            sort(buf.begin(), buf.end());
            string name = "chunk" + to_string(chunk++) + ".tmp";
            ofstream out(name);
            for (int v : buf) out << v << "\n";
            tmpFiles.push_back(name);
            buf.clear();
        }
    }
    // 省略最后一块写盘与多路归并实现，展示思路
    cerr << "chunks: " << tmpFiles.size() << "\n";
}

场景 4：前端排序展示（JavaScript）

背景：表格需要按多列排序，且保持相同 key 的相对顺序（稳定）。 为何适用：现代浏览器的 Array.prototype.sort 在大多数实现中稳定；如需保证，先映射索引再排序。

const rows = [
  { price: 100, sales: 50 },
  { price: 100, sales: 120 },
  { price: 80, sales: 200 },
];

rows
  .map((row, idx) => ({ ...row, idx }))
  .sort((a, b) => a.price - b.price || a.idx - b.idx)
  .forEach(r => console.log(r));

R — Reflection（反思与深入）

• 复杂度与空间：
  • O(n log n) 主力：归并（稳定、非原地）、快排（原地，最坏退化）、堆排（原地，缓存不友好）。
  • O(n + k) 非比较：计数/桶/基数，前提是范围/位数受限。
  • O(n^2) 基线：冒泡/选择/插入，适合教学或小数组。
• 替代方案对比：
  • 外部排序 vs 内存排序：数据超过内存时必须分块 + 归并。
  • TimSort vs 纯归并：TimSort 对局部有序数据更快且稳定，是工程首选。
  • Introsort vs 纯快排：通过递归深度回退到堆排，避免最坏 O(n^2)。
• 为何当前选型合理：
  • 稳定性优先：归并/Timsort/计数/基数；
  • 内存优先：快排/堆排/Introsort（原地）；
  • 范围可知：计数/桶/基数；
  • 超大数据：外部归并，多路合并 + 流式读取。

S — Summary（总结）

• 排序选型四要素：数据规模、数据分布、稳定性需求、内存/外存限制。
• 工程默认用语言内置排序（多为 TimSort/Introsort），特殊场景再自定义。
• 非比较排序在范围/位数受限时能把复杂度降到 O(n + k)。
• 外部排序是处理超大数据的必备技能，核心是分块 + 多路归并。
• 先定评价指标（时间、空间、稳定性），再选算法，避免盲选快排。

实践指南 / 步骤

• 步骤 1：评估数据规模与分布（随机/几乎有序/重复多）。
• 步骤 2：明确稳定性需求与内存上限。
• 步骤 3：对照上表选基准算法；若在 Python/Java，首选内置稳定排序。
• 步骤 4：写 3 组边界测试：全相等、逆序、几乎有序。
• 步骤 5：对大数据进行基准测试，并记录耗时/内存。

可运行示例（快速基准雏形，Python）

import random, time

def bench(n=100000):
    arr = [random.randint(0, 1000000) for _ in range(n)]
    t0 = time.time(); sorted(arr); t1 = time.time()
    print(f"n={n}, timsort time={t1 - t0:.3f}s")

if __name__ == "__main__":
    bench(200000)

常见问题与注意事项

• 误用 Array.sort / sort.Slice 时忘记 comparator 返回逻辑，导致不稳定或 NaN 问题。
• 快排枢轴固定取首元素 → 在有序数组上退化；需随机或三数取中。
• 计数/桶排序忽略范围，导致内存爆炸；需预估最大最小值。
• 外部排序若临时文件过多，需要 k 路归并或分批归并以控制句柄数。

最佳实践与建议

• 生产优先使用标准库排序，除非有明确范围/稳定性/外部排序需求。
• 写排序前先写 comparator 和测试，确保排序字段与稳定性符合需求。
• 对大规模数据进行抽样分析，判断是否适合桶/基数或需要外部排序。
• 在 PR 模板中要求标注“排序算法与理由”，便于审查。

小结 / 结论

• 本文给出排序选型的 ACERS 序章，为后续每个算法的细节铺路。
• 下一步可按系列目录展开：O(n^2) 基线、希尔、归并、快排、堆、非比较、TimSort、Introsort、选型实战。

参考与延伸阅读

• CLRS《算法导论》排序章节
• Timsort 原论文与 CPython 源码 listobject.c
• C++ std::sort / std::stable_sort 实现笔记
• PostgreSQL 外部排序实现（tuplesort）

元信息

• 阅读时长：约 12 分钟
• SEO 关键词：排序选型、算法稳定性、TimSort、Introsort、外部排序
• 元描述：排序专题序章，用 ACERS 框架梳理常见排序算法的复杂度、稳定性与工程场景，附多语言示例与选型清单。

行动号召（CTA）

• 按本文步骤为你的项目写一份“排序选型清单”，记录数据规模/分布/稳定性需求。
• 运行上面的 Python 基准，替换为你的真实数据分布做一次测试。
• 关注后续系列文章（快排、归并、堆、非比较、TimSort/Introsort）并尝试用 ACERS 模板复刻。