简介这份英文教学课件面向计算机专业学生与算法入门者聚焦数据结构中的排序主题帮助读者建立对基础排序算法的系统认识。课件从排序的基本概念讲起说明其作为最基础算法问题的重要性并指出排序在二分查找、相邻对、元素唯一性、频率统计等场景中的关键作用。内容重点讲解插入排序、冒泡排序和选择排序三种简单算法逐一分析其工作原理、适用条件与时间复杂度差异同时讨论升序降序、相等键值处理、非数值数据排序以及稳定性等核心议题并区分内部排序与外部排序的适用边界。资源为单个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 # 每轮结束后末尾 i1 个元素已有序 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] keyC 里要改成while (j 0 a[j] key)否则会漏掉第一个元素。第二个细节Bubble Sort 的提前退出标志必须每轮重置放在外层循环内部、内层循环之前。第三个细节Selection Sort 找最小值时内层循环从i1开始不要从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})跑出来你会看到n100 时 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, keynatural_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导致越界或漏排。解决拿 n2 和 n3 的最小用例手动走一遍或者用上面的计数器脚本跑随机数据对比 Python 内置sorted的结果。4.2 现象程序在大量数据上跑得极慢甚至卡死原因把 O(n²) 排序用在了 n10 万的数据上。Selection Sort 在 n10 万时比较次数约 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 比较次数。数据形态至少覆盖随机、有序、逆序、近乎有序四种。截图放运行结果和计数器输出不要只放一个排序后的数组那样看不出工作量。数据规模数据形态InsertionBubbleSelection100随机约 2500约 49504950100有序99994950100逆序495049504950100近乎有序约 300约 48004950这张表填进去再配一段分析“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这类英文课件给的是骨架真正让骨架长出血肉的是这些可观测的计数器和边界用例。希望帮到你。本文还有配套的精品资源点击获取