CSP-S 提高级 · CSP 2019 提高级第一轮 第 7 题

排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

排序稳定性核心看‘相等元素相对顺序是否被破坏’。快速排序分区时左右指针跳跃交换，相等元素极易越界，直接锁定它。

学生常把‘快排效率高’误当成‘稳定’，或以为归并排序合并时随便放就行。其实归并是左半边先放，天然稳定；快排的双向扫描会让相等元素互换位置，这是硬伤。

Q7 排序算法的稳定性

考察知识点

• 排序算法稳定性的定义与判断
• 常见排序算法（冒泡、插入、快排、归并）的稳定性属性

概念定义

排序稳定性：若序列中存在两个相等元素 $a_i = a_j$（$i < j$），排序后 $a_i$ 仍在 $a_j$ 之前，则称该排序是稳定的。简单说，相等元素的原始相对顺序不能乱。

逐步推导

逐项判断：

• A. 冒泡排序：只比较相邻元素，相等时不交换，稳定 ✅ → 不是本题答案
• B. 直接插入排序：插入到相等元素后面，不改变顺序，稳定 ✅ → 不是本题答案
• C. 快速排序：分区（partition）时，以枢轴为界，相等元素可能越过对方，不稳定 ❌ → 本题答案
• D. 归并排序：合并时左半边的相等元素先放入，稳定 ✅ → 不是本题答案

避坑指南

• 稳定 ≠ 效率高：稳定性和时间复杂度是两个独立维度
• 快速排序不稳定原因：a[j] <= pivot 和 a[i] >= pivot 的双向扫描会打乱相等元素的相对顺序
• 选择排序不稳定原因：每次选最小与当前位置交换，可能将前面的相等元素换到后面

技巧总结

• 记忆口诀："冒泡插排归并稳，快选堆希都不稳"
• 判断方法：看是否存在"远距离交换"——稳定排序通常只交换相邻元素
• 实际应用中，若需要稳定排序，常用归并排序

考频与趋势

排序基础在题库中高频出现，共 249 题，覆盖 9 个考试级别。其中快速排序单独考过 53 题，归并排序 51 题，两者都是排序稳定性考查的重灾区。从近年分布看，2023 年快速排序考了 6 题，2024 年 15 题，2025 年 14 题，2026 年 7 题，呈现持续高热度。归并排序同样在 2024 年达到 14 题、2025 年 15 题，说明命题人偏爱在排序稳定性上深挖。CSP 提高级近年共考过 9 题排序相关，其中快速排序和归并排序各占 3 题，显示提高级对两者稳定性辨析要求不低。

预测

基于快速排序和归并排序在 2023-2026 年间的高频考查（快速排序 2024 年 15 题、2025 年 14 题；归并排序 2024 年 14 题、2025 年 15 题），预计未来 CSP 提高级或 NOIP 初赛仍会重点考查排序稳定性，尤其是快速排序的分区细节和归并排序的合并规则。暂无足够依据预测具体年份题型变化，但稳定性辨析大概率持续作为单选或填空考点。