信息技术大学
排序算法
数据结构与算法·面试高频 · 第 3 章 排序与查找
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
排序算法
数据结构与算法·面试高频 · 第 3 章 排序与查找
快速排序与优化
选轴分区递归：平均 O(n log n)，怕有序数组，三招优化稳军心。
分区
选 pivot，小的丢左大的丢右，轴归位
随机轴
随机或三数取中，防有序输入退化
小区间
小区间换插入排序，省递归开销
最坏
轴每次最偏则 O(n²)，随机化后概率归零
归并排序与外部排序
分半排序再合并：稳定 O(n log n)，不依赖内存体量，外存的救星。
分治
递归分半，两段有序数组线性合并
稳定
相等元素保原序，链表排序天然合适
外部排序
内存装不下分块排，再多路归并
堆排序与 TopK
建堆 O(n)，逐个取顶：堆是「部分有序」的哲学，TopK 不必全排序。
建堆
自底向上逐个下沉，整体 O(n)
排序
堆顶与尾部交换后下沉，循环 n 次
TopK
K 大小的小根堆，O(n log k) 免全排
桶/计数/基数排序
不比较也能排：值域窄用计数，均匀分布用桶，多位数用基数。
计数
值域 k 小时统计频次，直接还原序列
桶
均匀散入桶内各排，期望线性
基数
按位做稳定排序，低位到高位多轮
稳定性与复杂度速查表
一张表定选型：快排平均最快，要稳定找归并，内存紧张用堆排序。
平均最快
快排常数小、缓存友好，日常首选
要稳定
归并/插入/计数保序，快排堆排不稳
空间
归并 O(n)，堆排原地 O(1)
本节要点
- ✓快排随机轴，防有序退化
- ✓归并稳定，外排多路归并
- ✓建堆 O(n)，TopK 用 K 堆
- ✓值域窄计数，均匀桶，多位基数
延伸主题：手撕快排并讲优化给场景选排序说理由
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么工程排序多是「快排为骨、多算法混合」？
参考答案快排平均最快，但小区间与近有序段不划算：小区间换插入排序、递归过深换堆排防退化（introsort 思路）。取各家之长，最坏情形也有保障。
2外部排序为什么要「多路归并」而不是二路？
参考答案归并趟数等于块数取对数；路数越多趟数越少，磁盘读写次数直线下降。路数受内存缓冲区数量限制，本质是 IO 与内存的折中。
3稳定性在什么业务里是真需求？
参考答案多关键字排序：先按日期排再按金额稳定排，金额相同者保持日期先后；表格多列连续排序同理。不稳定算法会打乱先前的次序，需求即崩。