定义#

排序（Sorting）是将一组数据元素按照关键字的递增（或递减）顺序重新排列的过程。

设有 n 个记录的序列 {R₁, R₂, …, Rₙ}，其对应关键字为 {k₁, k₂, …, kₙ}。排序就是确定一个排列 p₁, p₂, …, pₙ，使得 k(p₁) ≤ k(p₂) ≤ … ≤ k(pₙ)。

内部排序与外部排序#

408 考纲中绝大多数是内部排序，外部排序单独作为一个考点。

稳定性#

稳定性是区分排序算法的关键指标之一。

定义：若排序前后，关键字相同的两个元素的相对顺序保持不变，则称该排序算法是稳定的；否则是不稳定的。

判断方法：

• 判断不稳定 → 只需找到一个反例
• 判断稳定 → 需要严格证明

排序算法分类#

评价指标#

比较类排序的下界：基于比较的排序算法，最坏情况至少需要 O(n log n) 次比较。证明：n 个元素有 n! 种排列，判定树至少需要 ⌈log₂(n!)⌉ 层，由 Stirling 公式得 Ω(n log n)。基数排序不基于比较，因此可以突破这个下界。

排序过程中的”趟”#

408 真题常问”第 k 趟排序后的结果”，不同排序算法中”一趟”的含义不同：

考研高频考点#

• ⭐ 排序稳定性判断（选择题必考）
• ⭐ 各排序算法的时间/空间复杂度对比（选择题高频）
• ⭐ 根据场景选择排序算法（综合题）
• ⭐ “第 k 趟排序后的序列”的推导（选择题/填空题）
• 比较类排序的 O(n log n) 下界（概念题）
• 内部排序与外部排序的区分

易错：排序的稳定性与效率无关。快速排序平均最快但不稳定，归并排序稳定但需要 O(n) 额外空间——没有”全面最优”的排序算法。

算法总览#

关联页面#

• 插入排序 — 直接插入、折半插入、希尔
• 交换排序 — 冒泡、快速
• 选择排序 — 简单选择、堆
• 归并排序 — 二路归并
• 非比较排序 — 基数、计数
• 外部排序