NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 18 题

下列算法中，（ ）是稳定的排序算法。

拿到这种排序稳定性题目，别急着背口诀，直接看算法核心逻辑：相等元素在比较过程中会不会因为交换位置而打乱顺序。插入排序是逐个把元素插到前面，遇到相等的就插在后面，天然保持相对顺序；而快排、堆排、希尔排序在调整过程中都可能导致相等元素互换，所以不稳定。

很多学生死记'快选堆希'不稳定，却忘了插入、冒泡、归并是稳定的，遇到单选题容易犹豫。另外，希尔排序本质是优化版插入排序，但它改变了插入间隔，打乱了稳定性，这点容易被忽略。

考点概念：排序稳定性

排序算法的稳定性，指的是：当待排序的两个元素值相等时，它们在排序前后的相对位置是否保持不变。如果相等元素的先后顺序没变，就是稳定排序；一旦因为算法内部的交换操作导致相等元素前后颠倒，就是不稳定的。这在实际应用中很重要，比如先按成绩排序，再按学号排序，如果成绩相同的学生学号顺序乱了，就失去了二次排序的意义。

命题视角：为什么考这个？

命题人喜欢用这种纯概念题考察学生对算法本质的理解，而不是死记硬背。他们会在选项里放几个名字很像的算法（比如希尔排序和插入排序），看学生是否真正理解它们的工作机制。这道题的陷阱就在于：希尔排序虽然源自插入排序，但它通过分组跳跃式插入，破坏了稳定性，而插入排序则是逐个插入，遇到相等元素直接插在后面，完全不会打乱顺序。