Olverae Assets

1 先看：两个 90 分，排完谁在前？

五个同学按原始名单顺序站好（左上角圆圈是原始编号）。现在按分数从高到低排。两个 90 分的 ①小明和 ④小美——排完谁在前面？点两个按钮各试一次。

按分数从高到低排

点上面任一按钮，看两个 90 分的相对位置会不会变。

「稳定排序」≈ 插入排序 / 归并排序的行为；「不稳定排序」≈ 选择排序 / 快速排序的行为。两者排完分数都对，差别只在相等分数之间的先后。

你刚看到的就是「稳定」：排序时键（分数）相等的元素，保持它们在原数组里的先后顺序，就叫稳定排序；会打乱这个先后的，就是不稳定排序。

注意：不稳定 ≠ 排错。两种排完分数都正确——稳定性只管「分数一样时，谁排前面」这一件事。

2 谁稳定、谁不稳定（以及为什么）

不用死记——记住一句话：只做「相邻交换」的排序天生稳定；会「远距离搬运 / 跳着选」的排序容易把相等元素甩过头。

排序算法	稳定？	为什么
插入排序 Insertion	稳定	只在相等时停手不越过（用 > 而非 >= 比较），相等元素永远不互相跨越。
归并排序 Merge	稳定	合并时两边相等，固定先取左半（原来靠前的那个），先后就保住了。
冒泡排序 Bubble	稳定	只交换相邻且严格逆序的一对，相等的不换。
计数 / 基数排序	稳定	按出现顺序回填；基数排序正是靠稳定性一位一位排才成立。
选择排序 Selection	不稳定	每轮把最小值远距离换到前面，这一换可能把它甩到某个相等元素的前面。
快速排序 Quick	不稳定	分区时元素被跨越大段距离交换，相等元素的先后无法保证。
堆排序 Heap	不稳定	建堆 / 下沉会把元素在数组里跳跃式移动，先后被打乱。

想稳定又想快？常见做法是给每个元素带上原始下标当第二关键字：分数相同就比原下标，人为把不稳定排序「钉」成稳定。

3 这事什么时候要命：多关键字排序

单看一个 key，稳不稳定常常无所谓。真正要命的是多关键字：要「先按班级，同班再按分数」。标准技巧是从次要键到主要键，连续做稳定排序——靠的就是稳定性。下面一步步看。

目标：按班级升序，同班内按分数降序

原始名单（乱序）。先做第 1 步。

关键点：第 2 步按班级排时，同一个班的几个人分数早已在第 1 步排好。因为第 2 步是稳定的，它不会打乱同班这几个人的先后——于是「同班按分数」自动成立。如果第 2 步用了不稳定排序，同班内部的分数顺序就会被打乱，前功尽弃。

4 自测

三道题，点选项即时判对错。

去做例题：带原始下标做"稳定快排"

去做例题

一句话带走：

稳定 = 键相等时保持原相对顺序。它不影响排序对错，只决定「平手时谁在前」。相邻交换的排序（插入 / 归并 / 冒泡 / 计数）天生稳定；远距离搬运的（选择 / 快排 / 堆）默认不稳定，想稳定就把原始下标当第二关键字。真正用得上它的场景是多关键字排序——从次要键到主要键连续做稳定排序，平手自动由上一轮的顺序决定。