稳定排序到底有什么用？一个被忽视却决定成败的细节

在学插入、冒泡（稳定）和选择（不稳定）时，很多人把"稳定性"当成考试冷知识。但在工程里，稳定性常常决定一个排序能不能用。

场景一：多关键字排序。假设有一张员工表，要求"先按部门升序、再按工资升序"。正确做法是：先按工资排，再对结果按部门稳定排序。因为稳定排序保证：同一部门内的员工，仍保持刚才的工资升序。如果用了不稳定的排序去排部门，工资的顺序会被打乱，结果就错了。数据库 ORDER BY dept, salary 底层正是依赖稳定性（或显式多列比较）来实现这一点。

场景二：基数排序的前提。基数排序从最低位到最高位逐趟排序，每一趟都必须稳定——否则高位排好的顺序会在低位处理时被破坏（见缺口 B5）。可以说，没有稳定排序，就没有高效的基数排序。

场景三：保留"先来后到"。在任务调度、订单处理中，值相等的任务往往希望"先提交的先执行"。稳定排序天然保留插入顺序（即提交顺序），而不稳定排序可能任意重排，引发公平性或 bug。

回到今天的三种排序：插入排序、冒泡排序稳定；选择排序不稳定。选择排序之所以不稳定，是因为它把"最小值"跨过一整段直接换到前面，可能越过与之相等的元素。这解释了为什么工业级排序（Timsort、introsort 的对象模式）都刻意保持稳定性——它不是锦上添花，而是正确性的一部分。

关联推荐

• 哈希表：为什么 Redis、Python 字典都靠它"秒查" — 另一个"细节决定性能"的数据结构
• 从冒泡到快排 — 排序全景中的稳定性位置
• 算法与问题求解入门 — 算法正确性从"循环不变量"说起