专升本笔记

主题

2.8 排序

计算机程序设计 · 数据结构 · 2.8 排序（零基础讲义）

排序 ​

🎯 一句话秒杀：排序是把乱序变成有序。核心就几个——冒泡（相邻交换）、选择（找最值）、插入（像打牌）、快排（分治划分）。

① 📊【历年真题考情】 ​

本章（排序）在广东专升本计算机统考中的位置：

项目结论
出题频次⭐⭐⭐⭐——2026 考纲全解标注"排序 ⭐⭐，会写过程、会比较算法"；时间复杂度+稳定性 4 年连续考点
常考题型单选（2021 单选9、2022 单选3、2026 单选16）、判断（2021 判断27/30）、计算（排序过程）
预估分值8~20 分 / 200 分（约 4%~10%）
考纲归属2026 考纲「算法」考点19（排序、复杂度）

考场真实出现过的高频题：

  • 2021 判断27：冒泡排序时间复杂度是 O(n)？→ 错（一般 O(n²)）
  • 2021 判断30：快速排序是不稳定排序 → 对
  • 2021 单选9：两有序表 n、m 个元素归并，最少比较次数 → n 次
  • 2022 单选3：冒泡升序 [49,38,65,97,76,13,27] 第一趟后 → 97 沉底
  • 2026 单选16：平均 O(n log n) 且需 O(n) 额外空间的排序 → 归并排序

🎯 学习目标：学完本章，你能 ① 手推冒泡每一趟的结果；② 手推快排第一趟划分（low/high 逐步）；③ 说出每个算法的稳定性/复杂度；④ 判断归并的比较次数和空间——这四类题就是本章真题的全部考法。

② 🗣️【零基础大白话引入】 ​

排序是什么？ 排序就是把乱序变成有序——像给全班同学按身高排队，像打牌时把牌按大小整理。

几个生活化比喻：

  • 冒泡排序 = 水池里的气泡：大的往上浮（或重的往下沉）。一趟一趟比相邻两个，把最大的"沉"到底部。
  • 选择排序 = 选秀：每轮从剩余选手里挑最矮的站到最前面。
  • 插入排序 = 打扑克：摸一张新牌，插到手里已排好的牌中。
  • 快速排序 = 分阵营：选一个"基准"，比它小的站左边，比它大的站右边，然后两边各自再分——分而治之。

稳定性是什么？ 想象全班按成绩排序，成绩相同的两个人，排序后原来在前的还在前 = 稳定；可能换位 = 不稳定。就像并列名次时"先到先得"（稳定）还是"随机"（不稳定）。

💡 本章主线：概念（稳定/复杂度）→ 冒泡 → 选择 → 插入 → 快排（重点）→ 归并/堆/希尔。考试最爱考"第一趟结果"和"复杂度/稳定性对比"。

③ 📖【正式核心知识点讲解】 ​

本章知识点 = 考纲要求 + 历年真题实际考过的内容。

3.1 排序基本概念 ​

分类 ​

分类标准类型说明
内外内排序数据全在内存（考试范围）
外排序数据在磁盘
稳定性稳定排序相等元素排序后相对顺序不变
不稳定排序可能改变相对顺序

🚨 红牌警告（2021 判断30 必考） ​

稳定性是考试常考概念！ 稳定：冒泡、插入、归并、基数 不稳定：选择、快排、希尔、堆 记法："快些选一堆"（快排/希尔/选择/堆）— 不稳定 ❌

✅ 2021 判断30："快速排序是不稳定排序" → 对（快排在"快些选一堆"名单里）

3.2 冒泡排序（2022 单选3 必考） ​

c
void BubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int flag = 0;  // 优化：没交换就提前结束
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j] > arr[j+1]) {   // 相邻比较
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
                flag = 1;
            }
        }
        if (!flag) break;  // 没交换说明已有序
    }
}
指标值
平均时间复杂度O(n²)
最好（已有序）O(n)
空间复杂度O(1)
稳定性✅ 稳定

3.2.1 冒泡逐趟完整手算表格（2022 单选3 必考） ​

真题：冒泡升序 [49, 38, 65, 97, 76, 13, 27]，第一趟后结果？

第一趟过程（相邻两两比较，大的往后换）：

步骤比较交换？数组状态
149 vs 38✅ 换[38, 49, 65, 97, 76, 13, 27]
249 vs 65❌[38, 49, 65, 97, 76, 13, 27]
365 vs 97❌[38, 49, 65, 97, 76, 13, 27]
497 vs 76✅ 换[38, 49, 65, 76, 97, 13, 27]
597 vs 13✅ 换[38, 49, 65, 76, 13, 97, 27]
697 vs 27✅ 换[38, 49, 65, 76, 13, 27, 97]

✅ 第一趟结果：[38, 49, 65, 76, 13, 27, 97]——最大元素 97 沉底（2022 单选3） 记忆：冒泡一趟 = 最大的数沉到最底下

冒泡排序逐趟演化条形图（每趟最大值沉底）

完整四趟结果（直到有序）：

趟数结果沉底的数
初始[49, 38, 65, 97, 76, 13, 27]—
第1趟[38, 49, 65, 76, 13, 27, 97]97
第2趟[38, 49, 65, 13, 27, 76, 97]76
第3趟[38, 49, 13, 27, 65, 76, 97]65
第4趟[38, 13, 27, 49, 65, 76, 97]49
第5趟[13, 27, 38, 49, 65, 76, 97]38
第6趟[13, 27, 38, 49, 65, 76, 97]13

💡 手算技巧：每趟只看"还有几个数没沉底"，最大的永远先沉。

3.3 简单选择排序 ​

c
void SelectSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min = i;  // 找最小元素下标
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min]) min = j;
        if (min != i) {  // 交换
            int t = arr[i];
            arr[i] = arr[min];
            arr[min] = t;
        }
    }
}
指标值
时间复杂度O(n²)
空间复杂度O(1)
稳定性❌ 不稳定

💡 选择排序：每轮找最小放最前——像选秀，但"跳跃式交换"导致不稳定。

3.4 直接插入排序 ​

c
void InsertSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int temp = arr[i];  // 当前要插入的牌
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j+1] = arr[j];  // 后移
            j--;
        }
        arr[j+1] = temp;  // 插入到正确位置
    }
}

类比： 你打牌时摸到新牌，插到手里已排好序的牌中

指标值
平均时间复杂度O(n²)
最好（已有序）O(n)
空间复杂度O(1)
稳定性✅ 稳定

3.5 快速排序 ⭐（最重要！） ​

c
// 划分——选基准，比基准小的放左边，大的放右边
int Partition(int arr[], int low, int high) {
    int pivot = arr[low];  // 选第一个元素为基准
    while (low < high) {
        // 从右找小于基准的
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];  // 移到左边
        // 从左找大于基准的
        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];  // 移到右边
    }
    arr[low] = pivot;  // 基准归位
    return low;         // 返回基准位置
}

// 快速排序（递归）
void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pos = Partition(arr, low, high);  // 划分
        QuickSort(arr, low, pos - 1);         // 左子表
        QuickSort(arr, pos + 1, high);        // 右子表
    }
}

3.5.1 快排第一趟划分 low/high 逐步推演（计算题必考） ​

真题：对 [49, 38, 65, 97, 76, 13, 27] 快排，选 49 为基准，第一趟划分后？

"挖坑填数"逐步推演：

步骤lowhigh操作数组状态
006基准 pivot=49（挖坑）[空, 38, 65, 97, 76, 13, 27]
106右找 <49：high=6 是 27 <49 → 填到 low[27, 38, 65, 97, 76, 13, 空]
205左找 >49：low=2 是 65 >49 → 填到 high[27, 38, 空, 97, 76, 13, 65]
325右找 <49：high=5 是 13 <49 → 填到 low[27, 38, 13, 97, 76, 空, 65]
424左找 >49：low=3 是 97 >49 → 填到 high[27, 38, 13, 空, 76, 97, 65]
534右找 <49：high=4 是 76 ≥49 → high-- → high=3，low==high 停止—
633基准归位：arr[3]=49[27, 38, 13, 49, 76, 97, 65]

✅ 第一趟划分结果：[27, 38, 13] 49 [76, 97, 65]——基准 49 左边都小、右边都大 记忆：挖坑填数——右找小的填左坑，左找大的填右坑，基准归位。

快速排序第一趟划分"挖坑填数"逐步过程（基准 49）

快排指标：

指标值
平均时间复杂度O(n log n)
最坏（已有序）O(n²)
空间复杂度O(log n)（递归栈）
稳定性❌ 不稳定

✅ 2021 判断30：快排不稳定 → 对 🔑 记忆：快排平均 O(n log n)，最坏 O(n²)（原数组有序时）；不稳定——"快些选一堆"之一

3.6 归并排序（2021 单选9 / 2026 单选16 必考） ​

c
// 归并：把两个有序表合成一个有序表
// 思想：分治——先分成两半各自排序，再合并
指标值
平均/最好/最坏O(n log n)（都稳定）
空间复杂度O(n)（需要辅助数组）
稳定性✅ 稳定

3.6.1 归并比较次数（2021 单选9） ​

两有序表 n、m 个元素（n≤m）归并，最少比较次数 = n 次

为什么是 n 次？ 短表每个元素最多和长表比较一次就插入：

  • 短表 n 个元素，每个都比较一次定位 → 最少 n 次
  • 最坏 m+n-1 次（两边交替）

✅ 2021 单选9：两有序表 n、m 个元素（n≤m）归并，最少比较次数 → A. n

3.6.2 归并场景选择（2026 单选16） ​

平均 O(n log n) 且通常需额外 O(n) 空间的排序 = 归并排序

选项平均复杂度O(n) 空间？结论
A. 冒泡O(n²)否❌
B. 直接插入O(n²)否❌
C. 归并排序O(n log n)是✅
D. 简单选择O(n²)否❌

✅ 2026 单选16：答案 C. 归并排序——分治二分 + 辅助数组归并，平均/最坏均 O(n log n)

3.7 其他排序 ​

算法平均最好最坏空间稳定
希尔排序O(n^1.3)O(n)O(n²)O(1)❌
归并排序O(n log n)O(n log n)O(n log n)O(n)✅
堆排序O(n log n)O(n log n)O(n log n)O(1)❌
基数排序O(d(n+r))——O(r)✅

3.8 排序算法对比总结 ​

按时间复杂度分 ​

类别算法特点
O(n²)冒泡、选择、插入简单，适合小数据量
O(n log n)快排、归并、堆高效，企业常用
O(n^1.3)希尔插入的改进
O(d(n+r))基数适合整数/字符串

🚨 红牌警告 ​

考试必考：给一堆数据，写出快排第一趟划分后的结果 步骤：选基准→右→找小→左移→左→找大→右移→重复→基准归位

④ 🧪【真题同源例题】 ​

例题 1：入门基础题（先热热身） ​

冒泡排序升序排列 [5, 2, 8, 1]，第一趟后的结果？

逐项推演：

步骤比较交换？数组
15 vs 2✅[2, 5, 8, 1]
25 vs 8❌[2, 5, 8, 1]
38 vs 1✅[2, 5, 1, 8]

✅ 第一趟结果：[2, 5, 1, 8]（最大 8 沉底）

例题 2：2022 真题改编（冒泡第一趟） ​

冒泡升序 [49, 38, 65, 97, 76, 13, 27]，第一趟后的结果是（　　）

A. [38, 49, 65, 27, 76, 13, 97]　　B. [38, 49, 65, 76, 13, 27, 97]

逐项推演：

  1. 相邻比较：49>38 换 → [38,49,65,97,76,13,27]
  2. 65 与 97 不换；97>76 换 → [38,49,65,76,97,13,27]
  3. 97>13 换 → [38,49,65,76,13,97,27]
  4. 97>27 换 → [38,49,65,76,13,27,97]
  5. 97 沉底

✅ 答案：B. [38, 49, 65, 76, 13, 27, 97]（2022 单选3 同款）

例题 3：2021 真题改编（归并比较次数） ​

两有序表 n、m 个元素（n≤m）归并，最少比较次数是（　　）

A. n　　B. m　　C. n-1　　D. m+n

逐项推演：

  1. 归并时，短表元素逐个与长表比较定位
  2. 短表 n 个元素，每个最多比较一次 → 最少 n 次
  3. 最坏才是 m+n-1（交替比较）
  4. 答案：A. n

✅ 对应 2021 单选9。记忆：归并最少比较 = 短表长度 n。

例题 4：2026 真题改编（归并场景） ​

下列排序算法中，平均时间复杂度 O(n log n) 且通常需额外 O(n) 空间的是（　　）

A. 冒泡排序　　B. 直接插入排序　　C. 归并排序　　D. 简单选择排序

逐项分析：

  1. A 冒泡：O(n²) ❌
  2. B 插入：O(n²) ❌
  3. C 归并：O(n log n) + O(n) 辅助空间 ✅
  4. D 选择：O(n²) ❌

✅ 答案 C（2026 单选16 原题）。记忆：归并"要空间换时间"（辅助数组 O(n)）。

例题 5：快排第一趟划分 ​

对 [49, 38, 65, 97, 76, 13, 27] 快排，选 49 为基准，第一趟划分后的结果？

"挖坑填数"逐步推演：

步骤lowhigh操作数组
006pivot=49（挖坑）[空,38,65,97,76,13,27]
106右 27<49 填左坑[27,38,65,97,76,13,空]
205左 65>49 填右坑[27,38,空,97,76,13,65]
325右 13<49 填左坑[27,38,13,97,76,空,65]
424左 97>49 填右坑[27,38,13,空,76,97,65]
534右 76≥49 → high-- → 3==3 停—
633基准归位 49[27,38,13,49,76,97,65]

✅ 第一趟结果：[27, 38, 13] 49 [76, 97, 65]——49 左边全小、右边全大

⑤ ⚠️【历年真题高频扣分坑】 ​

#陷阱错误做法正确做法出处
1稳定性记反快排当稳定快排/选择/希尔/堆不稳定2021 判断30
2冒泡第一趟不知道最大沉底一趟把最大沉到末尾2022 单选3
3冒泡复杂度以为 O(n)一般 O(n²)，已有序才 O(n)2021 判断27
4归并空间以为 O(1)归并需 O(n) 辅助数组2026 单选16
5归并比较次数算成 m+n最少 n 次（短表）2021 单选9
6快排划分错基准位置放错挖坑填数，基准最后归位经典
7快排最坏以为快排最坏也 O(n log n)已有序时最坏 O(n²)经典
8堆排序空间以为堆需 O(n) 空间堆 O(1) 空间经典
9插入/冒泡稳定性以为冒泡不稳定冒泡/插入稳定经典
10归并最坏复杂度以为归并最坏变差归并平均/最坏都 O(n log n)2026 单选16

📌 最值钱的一条：第 2、6 条（冒泡第一趟 + 快排划分）是计算题核心——"逐趟/逐步画表"是排序题的拿分关键。

⑥ 📝【课后自测练习题】 ​

1. 冒泡升序 [5, 1, 4, 2, 8]，第一趟后的结果是（　　）（2022 真题风格）

A. [1, 4, 2, 5, 8]　　B. [1, 5, 4, 2, 8]　　C. [1, 2, 4, 5, 8]　　D. [5, 1, 2, 4, 8]

2. 两有序表 n、m 个元素（n≤m）归并，最少比较次数是（　　）（2021 真题风格）

A. n　　B. m　　C. n-1　　D. m+n

3. 下列排序算法中，平均时间复杂度 O(n log n) 且需额外 O(n) 空间的是（　　）（2026 真题风格）

A. 冒泡　　B. 插入　　C. 归并　　D. 选择

4. 对 [30, 20, 10, 40, 50] 快排（基准 30），第一趟划分后的结果是（　　）（经典）

A. [10, 20] 30 [40, 50]　　B. [20, 10] 30 [40, 50]　　C. [10, 30] 20 [40, 50]　　D. [20] 30 [10, 40, 50]

5. 判断：直接插入排序是稳定排序。（　　）（2021 真题风格）

A. 正确　　B. 错误

👆 点击展开参考答案与解析

第1题：A. [1, 4, 2, 5, 8]

  • 相邻比较：5>1 换 → [1,5,4,2,8]；5>4 换 → [1,4,5,2,8]；5>2 换 → [1,4,2,5,8]；5<8 不换
  • 最大 8 已在末尾，第一趟结束

第2题：A. n

  • 归并最少比较 = 短表长度 n（每个短表元素最多比较一次）

第3题：C. 归并

  • 归并 O(n log n) + O(n) 辅助数组（2026 单选16 原题）

第4题：B. [20, 10] 30 [40, 50]

  • 挖坑填数：pivot=30；右 50≥30 → high--；右 40≥30 → high--；右 10<30 填左坑 → [10,20,空,40,50]；左 20<30 → low++；low==high 归位 → [20,10,30,40,50]

第5题：A. 正确

  • 插入排序稳定（相邻后移不改变相等元素相对顺序）

📝 原有闭卷真题挑战（保留原内容 + 扩充至 10 题） ​

（点击下方空白查看答案）

1. 哪些排序算法是稳定的？哪些是不稳定的？

2. 快速排序的划分过程一次后，基准元素的位置？

3. 对 [38, 27, 43, 3, 9, 82, 10] 快排第一趟后的结果？

4. 冒泡排序的最好时间复杂度是多少？什么情况下出现？

5. 直接插入排序的类比理解？

（扩充题）

6. 冒泡升序 [6, 3, 8, 2, 5]，第一趟后的结果？

7. 两有序表 5、8 个元素归并，最少比较次数？

8. 下列哪个是稳定排序？ A.快排 B.选择 C.堆 D.插入

9. 快排对 [49,38,65,97,76,13,27] 第一趟划分（基准49）后？

10. 归并排序的空间复杂度？
👆 点击展开答案

  1. 稳定： 冒泡、插入、归并、基数；不稳定： 快排、选择、希尔、堆

  2. 基准元素最终放在它排序后应在的位置——左边都小，右边都大

  3. 选38为基准：最终一趟：[10, 27, 3, 9] 38 [43, 82]

  4. O(n) — 数组已经有序时（只需比较n-1次，不用交换）

  5. 像打扑克牌——摸一张新牌，插到手里已排好序的牌中

  6. 第一趟后：[3, 6, 2, 5, 8]（最大 8 沉底）

  7. 最少 5 次（短表长度 n=5）

  8. D. 插入（快排/选择/堆都不稳定）

  9. [27, 38, 13] 49 [76, 97, 65]（挖坑填数，基准归位）

  10. O(n)（需要辅助数组）

📖 教材习题对照 ​

教材习题知识点难度
习题10.1~10.2排序基本概念+分类⭐
习题10.3~10.4插入排序⭐⭐
习题10.5~10.6冒泡排序⭐⭐
习题10.7~10.8快速排序⭐⭐⭐⭐
习题10.9~10.10选择排序⭐⭐
习题10.11~10.12归并排序⭐⭐⭐

对应教材：严蔚敏《数据结构》C语言版 第2版 → 第10章 排序 对应考试大纲：考点19 — 排序

📺 配套视频 ​

复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。

仅供个人学习 · 考生回忆版 · 非考试院原卷

内容整理自公开回忆版与个人 Obsidian 笔记