NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 19 题

排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：

这题考排序算法的稳定性，直接背口诀'插冒归基'就行，剩下几个常见算法如快排、堆排、选择排、希尔排都是不稳定的，记住这个分类就能秒杀。

学生最容易把快速排序误认为稳定，因为快排逻辑简单，但它的交换是跳跃式的，一旦遇到相等元素就会打乱相对顺序；还有少数人觉得冒泡排序不稳定，其实冒泡只交换相邻且大小不同的元素，相等时不动，天然保证稳定性。

考点与概念

排序算法的稳定性，通俗讲就是：如果两个关键码相同的记录，在排序前后它们的相对位置保持不变，那这个算法就是稳定的。考试里常考的就是让你判断哪些算法稳定，哪些不稳定。

命题人怎么挖坑

这道题四个选项全是稳定算法，命题人想考的是你对不稳定算法的熟悉程度。很多学生死记硬背了'快速排序不稳定'，却忘了'选择排序、希尔排序、堆排序'也不稳定，导致在多选题里犹豫。记住，不稳定的算法通常涉及元素的跳跃式交换或随机选择，容易把相同元素的顺序打乱。