NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 17 题

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

拿到题先别急着背结论，直接想：这个排序算法里，相同元素会不会因为‘交换’动作而变顺序？冒泡、插入、归并都是‘冒泡’或‘有序插入’，同值只比不比不换；快排却靠基准把左右两半‘洗牌’，同值很可能被跨半区交换，这就是不稳的根源。

最容易把快排当成稳定排序，因为平时只记‘快排最快’，却忘了它用基准划分时，左右区间里相同键值元素的相对位置会被打乱。另一种坑是误以为归并排序不稳定，其实归并时‘左半部分相同元素先放’天然保证稳定。还有同学会纠结‘交换’的具体实现细节，把快排的不稳归咎于‘交换次数多’，其实关键不是交换次数，而是交换是否跨越了同值元素。

排序算法的稳定性，核心定义很简单：关键码相同的记录，排序前后相对位置不变。换句话说，如果原序列里 A 和 B 值相等且 A 在 B 前面，排完序后 A 依然要在 B 前面。冒泡排序每次只交换相邻且逆序的元素，同值相邻时不会交换，所以稳定；插入排序是把当前元素放到前面有序序列的合适位置，同值时放在后面，也不破坏顺序，稳定；归并排序合并两个有序子序列时，遇到相等元素规定‘左子序列的元素先放’，同样稳定。

命题人爱考这个点，通常不是让你现场写代码，而是让你判断哪个算法‘不稳定’，或者给出一个具体序列让你验证稳定性。快排之所以不稳定，是因为它用基准元素把数组分成左右两半，然后递归排序。在划分过程中，基准可能与远方的同值元素交换，导致原本在基准左侧的同值元素跑到右侧，相对顺序被颠倒。比如序列[3a, 2, 3b, 1]（3a 和 3b 值相等但 a 在前），选 3a 为基准后，3b 会被换到左边，最终 3b 在 3a 前面，顺序变了。这就是快排不稳的本质：划分时的跨区交换会打乱同值元素的相对位置。

考频上看，排序基础是高频考点，近五年（2023-2026）单年考到 22-57 题不等，说明命题人持续重视。归并排序单独考了 51 题，快排考了 53 题，两者都是重点，但快排的不稳定性在普及组初赛里反复出现，属于必会概念。趋势上，随着题目难度提升，单纯问‘是否稳定’可能会结合具体序列或让比较多种排序的稳定性，甚至考察不稳定排序的改进方案（如三路快排）。暂无足够依据预测未来具体题型，但快排不稳这个知识点本身不会变。

避坑提醒：别把‘快排不稳定’当成‘快排交换太多’，也别把‘归并排序不稳定’当成‘归并时顺序不确定’。记住定义，再看算法步骤里有没有‘跨区交换同值元素’的动作，就能快速判断。