DS-07-01 排序基本概念

408 > ### 数据结构 > #### 排序基本概念（稳定性/比较类/非比较类）

---

一、定位信息

维度	内容
章节归属	第7章 排序
知识单元编号	DS-07-01
前置知识	线性表、时间复杂度分析
后续衔接	DS-07-02 ~ DS-07-08 各类排序算法
考试大纲要求	理解排序的基本概念，掌握排序算法的分类方法
预计学习时长	20分钟

---

二、知识点讲解

1. 排序的定义

排序（Sorting） 是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。其形式化定义为：

给定含有 n 个记录的序列 R₁, R₂, …, Rₙ，其对应的关键字分别为 K₁, K₂, …, Kₙ，需确定一个排列 p₁, p₂, …, pₙ，使得 K_{p₁} ≤ K_{p₂} ≤ … ≤ K_{pₙ}（或 ≥），即将记录按关键字非递减（或非递增）的顺序排列。

2. 排序的稳定性

稳定性定义：若在待排序的序列中存在多个关键字相同的记录，假设 Kᵢ = Kⱼ（i ≠ j），在排序之前 Rᵢ 在 Rⱼ 之前，若排序之后 Rᵢ 仍在 Rⱼ 之前，则称该排序算法是稳定的；反之，若排序后 Rᵢ 可能在 Rⱼ 之后，则称该排序算法是不稳定的。

稳定性是算法的固有属性，与输入数据无关。

稳定排序：直接插入排序、冒泡排序、归并排序、基数排序

不稳定排序：简单选择排序、快速排序、希尔排序、堆排序

记忆口诀：「选快希堆不稳定」（选择、快速、希尔、堆——四个都不稳定）

3. 比较类排序与非比较类排序

分类	原理	时间复杂度下界	代表算法
比较类排序	通过比较关键字大小决定相对顺序	Ω(n log n)	插入、交换、选择、归并
非比较类排序	不通过比较，利用关键字的分布特性	可达 O(n)	计数排序、基数排序、桶排序

比较类排序的时间复杂度下界证明：n 个记录有 n! 种排列，每次比较排除一半，决策树高度至少为 ⌈log₂(n!)⌉ = Ω(n log n)。

4. 内部排序与外部排序

• 内部排序：待排序记录全部存放在内存中，整个排序过程不涉及数据的内、外存交换
• 外部排序：待排序记录数量很大，内存一次不能容纳全部记录，排序过程中需进行内、外存数据交换

5. 排序算法的一般框架（伪代码）

// 排序算法的一般输入输出描述
void Sort(ElementType A[], int n) {
    // 输入：数组 A[0..n-1]，含 n 个待排序元素
    // 输出：按关键字非递减排列的 A[0..n-1]
    // 核心操作：比较 + 移动（或交换）
    for (...) {
        // 比较：if (A[i].key > A[j].key)
        // 移动：A[k] = A[i]
        // 交换：swap(A[i], A[j])
    }
}

关键统计指标：

• 比较次数：算法执行过程中关键字的比较总次数
• 移动（赋值）次数：记录在数组中位置变动的总次数
• 辅助空间：除输入数据外额外使用的存储空间

---

三、记忆辅助

1. 稳定性口诀：「选快希堆不稳定」—— 简单选择、快速、希尔、堆排序四个不稳定
2. 比较类下界：n! 种排列 → 决策树 → 高度 ≥ ⌈log₂(n!)⌉ → Ω(n log n)，所以「比较排序不可能突破 O(n log n)」
3. 非比较类突破下界：计数/桶/基数排序不靠比较，可以 O(n)，但需要额外空间和特定条件
4. 内排 vs 外排：「内存够用 → 内排；数据太大放不下 → 外排」

---

四、例题精解

例题 1：判断排序算法的稳定性

题目：下列排序算法中，稳定的是（ ）。 A. 快速排序　　B. 简单选择排序　　C. 堆排序　　D. 归并排序

第一步：审题 题目要求选出稳定的排序算法，考查对各排序算法稳定性的记忆。

第二步：分析

• A. 快速排序：不稳定（如序列 [3, 3, 1]，一趟划分后两个 3 的相对顺序可能改变）
• B. 简单选择排序：不稳定（如序列 [5, 5, 3]，第 1 趟选最小值 3 与第 1 个 5 交换，两个 5 的相对顺序改变）
• C. 堆排序：不稳定（建堆和调整过程会破坏相同关键字的相对顺序）
• D. 归并排序：稳定（合并时当关键字相等时，优先取前半部分的元素）

第三步：解答 选 D。归并排序在合并过程中，当两个子序列关键字相等时，优先取前半部分元素，保证了稳定性。

第四步：总结 记住口诀「选快希堆不稳定」，其余内排算法（直接插入、冒泡、归并、基数）均为稳定排序。

---

例题 2：比较类排序的时间复杂度下界

题目：对 n 个不同关键字进行比较排序，最坏情况下比较次数的下界为（ ）。 A. O(n)　　B. O(n log n)　　C. O(n²)　　D. O(n³)

第一步：审题 题目考查比较类排序在最坏情况下的理论最优时间复杂度（下界）。

第二步：分析 n 个不同关键字有 n! 种排列。比较排序可用决策树模型分析：

• 决策树是二叉树，每个内部节点代表一次比较
• 每个叶节点代表一种排列结果
• 叶节点数 ≥ n!
• 二叉树高度 h 满足：2^h ≥ n!，即 h ≥ log₂(n!)
• 由 Stirling 公式：log₂(n!) ≈ n log₂n - n log₂e + O(log n) = Ω(n log n)

第三步：解答 选 B。比较类排序最坏情况下比较次数下界为 Ω(n log n)。

第四步：总结 任何基于比较的排序算法，在最坏情况下至少需要 Ω(n log n) 次比较。这是信息论下界，归并排序和堆排序达到了这个下界。

---

五、考情分析

年份	题型	考点	难度
近年高频	选择题	排序算法稳定性判断	★★☆
周期出现	选择题	比较排序时间复杂度下界	★★☆
偶尔涉及	应用题	选择合适排序算法解决实际问题	★★★

命题趋势：

• 稳定性判断是必考点，常以选择题形式出现
• 比较类排序下界证明偶尔考查，需理解决策树模型
• 内排与外排的区分、适用场景是综合题的基础

---

六、易错点

1. 稳定性记忆混淆：容易把堆排序误认为稳定（因为"堆"给人有序的感觉），实际堆排序不稳定
2. 下界理解偏差：O(n log n) 是比较排序的下界，但非比较排序（基数、计数、桶）可以突破这个下界达到 O(n)
3. 稳定性定义的边界条件：稳定性讨论的是「关键字相同」时的相对位置，若所有关键字互异，则任何排序算法都是稳定的
4. 内部排序 vs 外部排序的判断：不是看数据量大小，而是看排序过程是否需要内、外存交换

---

七、来源标注

• 《数据结构（C语言版）》严蔚敏，第10章 排序
• 《数据结构》王道考研，第7章 排序
• 408考试大纲：数据结构部分-排序基本概念
• 《算法导论》Thomas H. Cormen，第8章 线性时间排序（比较排序下界证明）