如何解读排序算法对比图表并以文字表述不同算法差异

图表解读逻辑 #

这类标准排序算法对比图的列基本是固定的，按列对应查看即可：

• 首列是算法名称，覆盖了从入门到工业级常用的所有排序实现
• 接下来三列分别对应最好情况时间复杂度、平均情况时间复杂度、最坏情况时间复杂度，复杂度里的n指代待排序的元素总量，O()标记是算法运行时间的增长量级，数值越小效率越高
• 再往后是空间复杂度列，标记算法运行需要消耗的额外内存，O(1)代表原地排序，不需要额外申请大量空间，数值越大占用内存越高
• 最后一列是稳定性，指排序后两个值相等的元素原有相对顺序会不会被保留，「稳定」代表顺序不变，「不稳定」代表顺序可能被打乱

不同排序算法的文字对比框架 #

你可以按复杂度、适用场景、优劣势三个维度统一对比，逻辑清晰不会乱：

1. 入门级小规模排序（冒泡、插入、选择） #

三者平均时间复杂度都是O(n²)，仅适合数据量不大的场景，一般做教学演示或者高级排序的补充逻辑用

• 冒泡排序：最好O(n)、平均O(n²)、最坏O(n²)，空间O(1)，稳定。实现逻辑最简单，但实际运行效率最低，工业界几乎不会直接用
• 插入排序：最好O(n)、平均O(n²)、最坏O(n²)，空间O(1)，稳定。对于接近有序的小规模数据效率极高，很多高级排序在处理到小数据分片时，都会降级用插入排序
• 选择排序：最好/平均/最坏都是O(n²)，空间O(1)，不稳定。因为要频繁交换未排序区间的最小元素，会打乱等值元素的原有顺序，实际运行效率不如插入排序

2. 工业级大规模排序（快排、归并、堆排） #

三者平均时间复杂度都是O(nlogn)，适合百万级以上的大量数据排序

• 快速排序：最好O(nlogn)、平均O(nlogn)、最坏O(n²)（仅轴点选择极差时才会触发，做了随机轴点优化后几乎不会出现），空间O(logn)（递归栈开销），不稳定。是目前工业界使用最广的排序算法，缓存命中率高，实际运行效率比同复杂度的另外两种算法高30%以上
• 归并排序：最好/平均/最坏都是O(nlogn)，空间O(n)，稳定。唯一的劣势是需要额外申请和待排序数据等量的内存空间，适合对排序稳定性有硬性要求的场景
• 堆排序：最好/平均/最坏都是O(nlogn)，空间O(1)，不稳定。优势是完全不需要递归，内存开销极小，适合嵌入式、内存吃紧的设备场景，缺点是缓存不友好，实际运行速度不如快排

3. 特殊场景排序（计数、基数、桶排） #

这类属于非比较排序，不需要靠元素大小比较决定顺序，时间复杂度可以突破O(nlogn)的比较排序理论下限，但对数据特征有严格要求

• 计数排序：时间复杂度O(n+k)（k是数据的取值范围大小），空间O(k)，稳定。仅适合数据取值范围很小的场景，比如排序用户年龄、考试分数这类场景
• 基数排序：时间复杂度O(d*(n+k))（d是数据的位数），空间O(n+k)，稳定。适合整数、字符串这类可以按位拆分排序的场景
• 桶排序：时间复杂度平均O(n)、最坏O(n²)，空间O(n+k)，稳定。需要提前把数据拆分到多个有序桶里，适合数据分布均匀的场景

内容的提问来源于stack exchange，提问作者bart