英文课件22_sorting_01.pdf精讲：插入、冒泡、选择排序的手写实现与避坑指南

简介：这份英文教学课件面向计算机专业学生与算法入门者，聚焦数据结构中的排序主题，帮助读者建立对基础排序算法的系统认识。课件从排序的基本概念讲起，说明其作为最基础算法问题的重要性，并指出排序在二分查找、相邻对、元素唯一性、频率统计等场景中的关键作用。内容重点讲解插入排序、冒泡排序和选择排序三种简单算法，逐一分析其工作原理、适用条件与时间复杂度差异，同时讨论升序降序、相等键值处理、非数值数据排序以及稳定性等核心议题，并区分内部排序与外部排序的适用边界。资源为单个PDF文件，压缩包约449KB，篇幅精炼，适合课堂配套学习或考前快速梳理。目前已有114人学习，可作为数据结构、数据分析与大数据挖掘方向打牢算法基础的入门材料。

1. 从一份英文课件说起：22_sorting_01.pdf 里到底藏着什么

如果你手头正好有一份名为22_sorting_01.pdf的英文教学课件，大概率是国外高校数据结构课程里排序章节的第一讲。这类课件通常不会一上来就甩代码，而是先用扑克牌、排队、图书馆书架这类生活场景把 Insertion Sort、Bubble Sort、Selection Sort 三种基础排序的直觉建立起来，再给出伪代码和复杂度分析。它解决的不是“怎么调库排序”，而是“排序这件事在计算机里为什么这样设计”。适合谁看？准备数据结构期末复习的学生、要交实验报告的本科生、刚转行想补算法底子的开发者，以及需要给新人讲清楚排序原理的工程师。热搜里“数据结构排序算法”“选择排序”“数据结构期末复习”这些词，恰好对应了这份课件的核心受众。但英文课件有个通病：定义严谨、例子抽象，看完觉得自己懂了，一写代码就卡在边界条件上。所以这篇笔记不逐页翻译课件，而是把它讲的三类排序拆成能跑、能改、能排错的落地路径，顺带把课件里没展开的坑补上。

2. Insertion Sort、Bubble Sort、Selection Sort 的选型逻辑与手写实现

2.1 三种排序的适用边界：为什么课件先讲它们

22_sorting_01.pdf把这三个放在最前面，不是因为它们最快，而是因为它们最能体现“排序”这件事的基本矛盾：比较、交换、移动。Insertion Sort 的核心是维护一个已排序前缀，每次把新元素插到正确位置，像整理手里的扑克牌。它的优势在近乎有序的数据上接近 O(n)，这也是为什么很多标准库在数组长度小于某个阈值时会退回插入排序。Bubble Sort 靠相邻交换把最大元素“冒”到末尾，教学价值大于实用价值，但它对“稳定性”的演示非常直观。Selection Sort 每轮选最小放到前面，交换次数最少，但比较次数固定，适合交换成本远高于比较成本的场景。

选型时看三个维度：数据规模、初始有序度、交换与比较的相对成本。数据量小于 50 且基本有序，Insertion Sort 往往比快排还快；数据量小但交换代价高，Selection Sort 更稳；Bubble Sort 除非是为了教学演示或面试手写，生产环境基本不用。课件里通常会给出三者最坏、平均、最好复杂度的表格，但不会告诉你实际跑起来缓存命中率的影响——Insertion Sort 的顺序访问模式对 CPU 缓存友好，这是它在小数组上表现优异的一个隐藏原因。

2.2 用 Python 把三种排序写成可复现的最小实现

下面这段代码不是照抄课件伪代码，而是加了边界处理和计数器的版本，方便你观察比较和交换次数。运行环境 Python 3.8+ 即可，不需要额外依赖。

def insertion_sort(arr): # 复制一份，避免修改原数组 a = arr[:] compares = 0 moves = 0 for i in range(1, len(a)): key = a[i] j = i - 1 # 从后往前找插入位置，同时右移元素 while j >= 0 and a[j] > key: compares += 1 a[j + 1] = a[j] j -= 1 moves += 1 # 最后一次比较失败也要计数 if j >= 0: compares += 1 a[j + 1] = key return a, compares, moves def bubble_sort(arr): a = arr[:] compares = 0 swaps = 0 n = len(a) for i in range(n - 1): swapped = False # 每轮结束后，末尾 i+1 个元素已有序 for j in range(n - 1 - i): compares += 1 if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] swaps += 1 swapped = True if not swapped: break return a, compares, swaps def selection_sort(arr): a = arr[:] compares = 0 swaps = 0 n = len(a) for i in range(n - 1): min_idx = i for j in range(i + 1, n): compares += 1 if a[j] < a[min_idx]: min_idx = j if min_idx != i: a[i], a[min_idx] = a[min_idx], a[i] swaps += 1 return a, compares, swaps if __name__ == "__main__": data = [5, 2, 9, 1, 5, 6] print("insertion:", insertion_sort(data)) print("bubble: ", bubble_sort(data)) print("selection:", selection_sort(data))

逻辑说明：Insertion Sort 里compares在 while 条件判断和循环结束后的补计都要算，否则会漏掉最后一次失败比较；moves统计的是元素右移次数，不是交换次数，因为插入排序本质是移动。Bubble Sort 加了swapped提前退出，这是课件里常被省略但实际必须写的优化，否则有序数组也要跑满 O(n²)。Selection Sort 只在min_idx != i时交换，避免自交换，这个细节在统计交换次数时会影响结果。

参数说明：输入是任意可比较元素的列表，返回排序后的新列表和两个计数器。如果你要排序的是字符串或自定义对象，把比较运算符换成对应的 key 函数即可，但注意 Python 里字符串比较是按字典序，和热搜里“字符串排序”“字母数字组合的排序”场景一致。跑一遍你会看到，同样六个元素，Insertion Sort 的比较次数通常少于 Selection Sort，但移动次数更多，这就是“比较与移动的权衡”。

2.3 把伪代码翻译成 C 语言时最容易丢的三个细节

很多数据结构实验报告要求用 C 实现，22_sorting_01.pdf的伪代码数组下标从 1 开始，直接翻译成 C 的 0 基下标会翻车。第一个细节：插入排序的内层循环边界，伪代码写while j > 0 and A[j] > key，C 里要改成while (j >= 0 && a[j] > key)，否则会漏掉第一个元素。第二个细节：Bubble Sort 的提前退出标志必须每轮重置，放在外层循环内部、内层循环之前。第三个细节：Selection Sort 找最小值时，内层循环从i+1开始，不要从i开始，否则会把自己和自己比较，虽然结果不错但比较次数虚高。

#include <stdio.h> void insertion_sort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } void bubble_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1; } } if (!swapped) break; } } void selection_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min_idx]) min_idx = j; } if (min_idx != i) { int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t; } } }

这段 C 代码可以直接编译运行，配合一个打印函数就能验证。注意 C 里没有 Python 的切片复制，传参时数组会退化成指针，所以排序会直接修改原数组，实验报告里如果要保留原数据，得自己 memcpy 一份。

3. 复杂度分析之外：课件没讲透的比较次数与稳定性

3.1 用计数器验证 O(n²) 到底是多少次比较

课件通常只给大 O 记号，但期末复习和实验报告经常要求具体比较次数。对 n 个元素，Selection Sort 的比较次数恒为 n(n-1)/2，和初始顺序无关。Bubble Sort 最坏也是 n(n-1)/2，最好情况（已有序且带提前退出）是 n-1 次。Insertion Sort 最坏 n(n-1)/2，最好 n-1 次。下面这段脚本可以生成不同规模、不同有序度的数据，把三个排序的比较次数打出来对比。

import random def build_cases(n): random.seed(42) return { "random": [random.randint(0, 10000) for _ in range(n)], "sorted": list(range(n)), "reversed": list(range(n, 0, -1)), "nearly": list(range(n)), } def nearly_sorted(n): a = list(range(n)) # 随机交换 5% 的元素，制造近乎有序 for _ in range(max(1, n // 20)): i = random.randint(0, n - 1) j = random.randint(0, n - 1) a[i], a[j] = a[j], a[i] return a for n in [10, 50, 100]: cases = build_cases(n) cases["nearly"] = nearly_sorted(n) print(f"--- n={n} ---") for name, data in cases.items(): _, c1, _ = insertion_sort(data) _, c2, _ = bubble_sort(data) _, c3, _ = selection_sort(data) print(f"{name:8s} insertion={c1:5d} bubble={c2:5d} selection={c3:5d}")

跑出来你会看到，n=100 时 Selection Sort 稳定在 4950 次比较，而 Insertion Sort 在 sorted 数据上只有 99 次，在 nearly 数据上也只有几百次。这就是为什么说“近乎有序时插入排序接近线性”。参数上，nearly_sorted里交换比例设为 5%，你可以改成 1% 或 10% 观察曲线变化。这个实验比背复杂度表有用得多，也是数据结构实验报告里容易拿分的地方。

3.2 稳定性：为什么 Selection Sort 是唯一不稳定的

稳定性指相等元素的相对顺序在排序后是否保持不变。Insertion Sort 稳定，因为它是逐个插入，遇到相等元素会停在后面。Bubble Sort 稳定，因为相邻交换只在严格大于时发生。Selection Sort 不稳定，经典反例是[5a, 5b, 2]，第一轮把 2 和 5a 交换，得到[2, 5b, 5a]，两个 5 的相对顺序变了。课件里可能只给一句“Selection Sort is not stable”，但考试和面试会追问反例。

如果你需要稳定排序又只能用这三种，优先 Insertion Sort 或 Bubble Sort。热搜里“组内123排序”“sql server 分组后组内”这类需求，本质上要求组内稳定，用 Selection Sort 会出问题。实际工程里 Python 的sorted和 Java 的Arrays.sort对对象数组都保证稳定，底层是 TimSort，但那是进阶内容，课件第一讲不会展开。

3.3 把排序接进真实数据：从整数到字符串与结构体

课件例子多是整数，但热搜里“字符串排序”“字母数字组合的排序”“pandas数据结构创建”说明真实数据更杂。Python 里字符串排序直接用<比较即可，但“a10”和“a2”会按字典序排成 a10 在前，这不是自然排序。如果需要自然排序，得把字符串拆成数字和非数字段。C 里排序结构体要传比较函数指针，或者用qsort配合自定义 cmp。下面给一个 Python 自然排序的 key 函数，能处理“file2”和“file10”这种混合串。

import re def natural_key(s): # 把字符串拆成数字段和非数字段，数字段转 int return [int(t) if t.isdigit() else t.lower() for t in re.split(r'(\d+)', s)] data = ["file10", "file2", "File1", "file20"] print(sorted(data, key=natural_key)) # 输出 ['File1', 'file2', 'file10', 'file20']

逻辑说明：re.split(r'(\d+)', s)会把字符串按数字段切开并保留数字，natural_key返回一个混合列表，Python 比较列表时逐项比较，数字段用 int 比，非数字段用字符串比。参数上，t.lower()是为了大小写不敏感，如果你要区分大小写就去掉。这个技巧在文件列表排序、版本号排序里很常用，也是课件不会讲但实际会遇到的。

4. 避坑与排查：手写排序时最常见的五类翻车

4.1 现象：排序结果基本对，但个别元素位置不对

原因：边界条件写错。Insertion Sort 内层循环写成j > 0而不是j >= 0，导致第一个元素永远不参与比较；Bubble Sort 内层循环写成j < n - i而不是j < n - 1 - i，导致越界或漏排。解决：拿 n=2 和 n=3 的最小用例手动走一遍，或者用上面的计数器脚本跑随机数据，对比 Python 内置sorted的结果。

4.2 现象：程序在大量数据上跑得极慢，甚至卡死

原因：把 O(n²) 排序用在了 n=10 万的数据上。Selection Sort 在 n=10 万时比较次数约 50 亿次，Python 里要跑几分钟。解决：先确认数据规模，超过几千就换 TimSort、快排或归并。课件讲基础排序是为了理解原理，不是让你在生产环境用。热搜里“java排序”“使用array类对数组排序”其实就是在提醒，实际开发优先用标准库。

4.3 现象：排序后相等元素的顺序变了，业务逻辑出错

原因：用了不稳定的 Selection Sort，或者自己写的比较函数在相等时返回了非零值。解决：需要稳定时改用 Insertion Sort 或标准库稳定排序；自定义比较函数确保相等返回 0。在 SQL 里ORDER BY不保证稳定，需要加次级排序键，这也是“sql server 分组后组内”排序要注意的点。

4.4 现象：C 语言里数组排序后原数据被改，实验报告对不上

原因：C 数组传参退化为指针，函数内排序直接改原数组。解决：在调用前memcpy一份副本，或者函数内部分配临时数组。Python 里如果直接传 list 也会改原数据，所以上面的实现都用了arr[:]复制。

4.5 现象：字符串排序结果和预期不一致，数字串乱序

原因：默认字典序把“10”排在“2”前面。解决：用自然排序 key，或者把数字部分补零对齐。如果数据来自 pandas，注意sort_values默认也是字典序，需要自定义 key 或先转换类型。

5. 从课件到实验报告：把 22_sorting_01.pdf 变成可提交的成果

5.1 实验报告里该放哪些表格和截图

数据结构实验报告通常要求：算法伪代码、C 或 Python 实现、测试用例、比较次数统计表、复杂度分析。你可以用第 3 章的脚本生成一张表，列分别是数据规模、数据形态、Insertion 比较次数、Bubble 比较次数、Selection 比较次数。数据形态至少覆盖随机、有序、逆序、近乎有序四种。截图放运行结果和计数器输出，不要只放一个排序后的数组，那样看不出工作量。

这张表填进去，再配一段分析“Insertion Sort 在近乎有序时比较次数远低于 Selection Sort，因为它的内层循环提前终止”，报告的技术含量就上来了。

5.2 用单元测试锁住边界，避免改代码改出回归

手写排序最容易在“改一点优化”时引入 bug。用 Python 的unittest或直接写断言，把空数组、单元素、全相等、已有序、逆序都覆盖。下面这段可以直接放进实验报告附录。

def test_sorting(): cases = [ [], [1], [2, 1], [1, 1, 1], [3, 2, 1], list(range(20)), list(range(20, 0, -1)), ] for c in cases: expected = sorted(c) assert insertion_sort(c)[0] == expected assert bubble_sort(c)[0] == expected assert selection_sort(c)[0] == expected print("all tests passed") test_sorting()

逻辑说明：sorted(c)是 Python 内置稳定排序，作为基准。空数组和单元素用例能抓出边界错误，全相等用例能抓出比较符号写成>=导致的不稳定。参数上，如果你改了排序实现，先跑这个测试再跑性能脚本。

5.3 一个我常用的习惯：先写计数器，再写排序

我带新人时发现，直接写排序很容易陷入“看起来对”的错觉。我的习惯是先把比较和交换的计数器框架搭好，再填排序逻辑，每改一次都能看到次数变化。如果次数突然从几千跳到几万，大概率是循环边界写错了。这个习惯让我少熬了很多夜。22_sorting_01.pdf这类英文课件给的是骨架，真正让骨架长出血肉的是这些可观测的计数器和边界用例。希望帮到你。

本文还有配套的精品资源，点击获取