稳定排序

一句话理解

稳定排序：相等元素保持原来的相对顺序。

为什么要学

多关键字时可以排完次关键字再稳定排主关键字。

讲解

sort 不稳定。stable_sort 稳定，稍慢一点。

若一次 cmp 写全所有关键字，就不依赖稳定性。

例子

原序列 (2,a) (1) (2,b)。稳定排序按数字：1, (2,a), (2,b)。不稳定可能 (2,b) 跑到 (2,a) 前。

常见错误

• 以为 sort 稳定。
• 既不稳定又不在 cmp 里写次关键字。