简介数据结构英文教学课件聚焦排序Sorting这一核心算法主题面向计算机专业学生及数据分析、大数据方向初学者旨在帮助读者理解如何高效组织与处理数据。排序被视作最基础的算法问题之一据称消耗了约25%的CPU运算时间也是二分查找等众多算法的关键前置步骤。课件从基本概念切入详细讲解比较函数、稳定性、升序/降序、相等键值及非数值数据排序等要点并系统剖析插入排序、冒泡排序、选择排序三种简单算法的原理、实现思路与适用场景同时比较了它们在最好与最坏情况下的时间复杂度差异还区分了内部排序与外部排序。另外课件延伸介绍了排序在最近点对、元素唯一性等实际问题中的应用有助于将基础算法能力迁移到大数据分析与数据挖掘场景。整份资源仅含1个PDF文件大小449KB内容精炼、结构清晰既适合打印阅读也便于在移动端随时翻阅。目前已有114人学习下载适合作为数据结构课程的英文补充课件或算法入门自学材料。1. 数据结构英文课件里的 sorting 第一讲为什么值得精读排序几乎是数据结构课程里第一个真正的分水岭话题。课件里有一个常被引用的统计计算机大约有四分之一的 CPU 周期都花在各种排序任务上这是“排序是数据结构核心问题”最直观的证据。这份来自大学计算机学院的数据结构英文课件主题是 Sorting_01也就是排序的第一讲内容收敛在三个最基础的简单排序算法插入排序、冒泡排序和选择排序。它的典型使用场景是你正准备期末复习、梳理考研数据结构里的排序部分或者想一次性把排序相关的英文术语和算法思想对照着吃透。它不是编程手册而是把基本概念、复杂度推导和算法流程放在同一份 PDF 里的教学课件适合在啃教材和做题之前先立起整体框架。2. 排序的基本概念比较器、稳定性与升序降序约定2.1 比较器与关键字段排序底层到底在比什么课件在正式讲三种排序算法之前先花了不少篇幅定义“排序”本身。它把排序描述成把一组任意排列的 n 个元素重新排列成某种全序关系。这里的关键不是“把数字排好”而是“用什么样的规则判断两个元素谁在前谁在后”。在课件里这个规则被抽象成comparator比较器。每个记录record里有一个“关键字段”key field比较器负责从记录中提取这个字段然后通过一个比较函数返回、或三种结果。也就是说排序算法本身不关心你排的是整数、字符串还是自定义对象它只依赖比较器给出的结论。写代码时最容易忽略的一点是比较器的返回值语义要统一。很多语言里排序接口只要求返回负数、零或正数但如果你把“大于”写反了整个排序结果就是反的。课件里专门提到同一个算法想实现升序或降序只需要把比较函数里的换成其余代码完全不用动。我一般在实现自定义对象排序时会单独写一个比较函数而不是直接依赖默认排序。比如按学生的学号排序学号是字符串但存的是数字这就需要在比较器里先做类型转换。课件里强调的“key field is extracted from the record by the comparator”就是这个意思比较器不只是比较它还负责“取出”关键字段这个动作很容易被初学者漏掉。2.2 稳定性相同键值记录的相对顺序问题稳定性stable是排序概念里最容易被一带而过、但实际工程中又很重要的性质。课件给的定义是如果两个记录的键值相同排序完成后它们的相对顺序和排序前保持一致那这个算法就是稳定的。举一个具体的业务场景一个成绩表先按班级排序再按分数排序。如果第二次排序用的是稳定算法那同一个分数段内的记录会保留第一次按班级排好的顺序如果用的是不稳定算法第二次排序可能会把班级顺序打乱。这就是为什么归并排序这种稳定算法在某些场景下比快排更受欢迎——不只是时间复杂度的问题。课件里接下来提到处理相等键值有三种策略一是无所谓排序结果里谁前谁后都行二是需要按次要键secondary key继续排序三是干脆保持它们在原始排列中的顺序。第三种策略正是稳定性要保证的东西。判断一个算法是否稳定最简单的办法是观察它是否“跨过”相等的元素进行交换或插入。比如插入排序在从后往前扫描时只有当当前元素严格小于已排序元素时才移动位置相等的元素不会发生交换所以它稳定。而选择排序里如果每次找最小值时遇到相等元素可能把靠前的那个换到后面去所以它不稳定。2.3 内部排序与外部排序数据量决定算法选型课件在“Terminology and Notation”这一节里提到了内部排序和外部排序的分类。内部排序Internal Sorting指所有数据都能一次性装入内存排序过程中不涉及内外存数据交换外部排序External Sorting则用于数据量超过内存容量的场景需要把数据分块读入内存、排序再写回外部存储最后归并。这个分类对实际选型非常关键。比如你在处理一个小数组时插入排序虽然最坏复杂度是 O(n²)但因为常数极小实测可能比快排还快但如果你处理的是几十 GB 的日志文件根本不可能全部 load 进内存那就得走外部排序的思路典型做法是“分块排序 多路归并”。课件里还有一句话值得注意它说传统分析排序算法时主要看两个指标一个是关键字的比较次数另一个是交换swap次数。第一个指标与运行时间强相关而且不依赖机器和数据类型第二个指标在记录体积很大时尤其重要因为移动一个大对象的代价可能远高于一次比较。提示在数据挖掘和数据分析场景里排序往往是数据预处理的一部分。对海量数据先排序再做相邻比较可以顺带解决重复检测、最邻近查找等问题这也是课件在“Applications”部分强调的思路。3. 插入排序从扑克牌理牌到复杂度三态分析3.1 插入排序的基本思路把新元素插入已排序区插入排序是所有排序算法里最贴近人类直觉的一种。课件里的比喻是整理手中的扑克牌你从左到右一张张拿牌每拿到一张就把它插入到已经排好序的那堆牌里的正确位置。还有一种常见比喻是整理电话账单看到一张新的账单就塞进已经按日期排好的账单堆里。用数组的语言描述维护一个“已排序前缀”初始时第一个元素自己构成一个有序区从第二个元素开始每次把当前元素从后往前与有序区里的元素逐个比较找到它应该插入的位置把该位置之后的元素整体后移一位再把当前元素放进去。这样有序区的长度每次增加 1直到整个数组都有序。这个“从后往前比较”的操作细节很关键。教材里常见的写法是先把当前元素暂存到一个临时变量里然后从有序区的最后一个元素开始只要该元素比当前元素大就把它往后挪一个位置挪完以后空出来的那个位置就是当前元素的插入点。课件里提到如果数据本身是链表而不是数组插入排序的实现会有所不同链表的插入不需要移动元素只需要修改指针但定位插入位置仍然要顺序扫描。这引出一个对实际复杂度的理解数组实现的插入排序代价集中在“移动元素”链表实现的插入排序代价集中在“比较查找位置”。两种数据结构下的常数差异很大这也是为什么课件专门花一段讲数组和链表在插入排序中的区别。3.2 数组实现与代码逐行对照这里我给出一个最常见的 C 风格插入排序实现和课件的数组思路一致void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { // i 从 1 开始arr[0] 视为已排序区 int key arr[i]; // 暂存当前待插入元素 int j i - 1; while (j 0 arr[j] key) { // 从后往前找插入位置 arr[j 1] arr[j]; // 比 key 大的元素后移一位 j--; } arr[j 1] key; // 把 key 放到空出来的位置 } }这段代码里最需要注意的地方是arr[j] key这个判断。它用的是而不是这一点直接决定了算法是否稳定只有严格大于当前元素的才会后移相等元素会停在原地所以相等的 key 会插入到已有序区中相等元素的后方相对顺序不变。key arr[i]这一步看起来简单但它是整个算法的安全保证。如果不暂存后面元素后移时会覆盖掉arr[i]的原始值导致数据丢失。很多初写插入排序的翻车现场都出在这里。j 1这个位置是插入点的原因在于while 循环结束有两种情况要么j已经小于 0说明 key 比当前有序区所有元素都小应该插到数组开头要么arr[j] key说明当前位置的左边是最后一个不比 key 大的元素key 应该插在它的右边也就是j 1。3.3 最好、最坏与平均复杂度三种情况差别极大插入排序最特别的地方在于它的最好、最坏、平均复杂度完全不同而且差距显著。很多初学者只记住了“O(n²)”这个笼统结论却不知道插入排序在近乎有序的数据上表现几乎线性。最好情况是数据已经升序排好。此时每次插入都只需要和有序区的最后一个元素比较一次发现它不大于 key直接原地不动既没有元素移动也没有进一步比较。n 个元素共 n-1 次插入每次只有一次比较总复杂度 O(n)。最坏情况是数据完全逆序。此时第 i 次插入需要把前面 i-1 个元素全部后移做 i-1 次比较和 i-1 次移动。把所有代价加起来比较总数是 12...(n-1) n(n-1)/2移动总数也接近这个量级复杂度 O(n²)。这个情况对应课件里的公式推导过程它是三种简单排序里最差的一种。平均情况比较微妙。课件里给出的推导思路是如果输入是随机排列第 i 次插入时key 落在任意位置的概率相等期望比较次数是 i/2 左右所以总期望复杂度是 O(n²) 但常数是最好情况的两倍关系具体是 n(n-1)/4 量级。结论是平均复杂度仍然 O(n²)但实际常数比最坏情况小一半。这也是为什么工程上会用它做“近乎有序数据”的兜底排序。比如在一个已经按时间排序的列表末尾追加少量新记录再整体排序一次插入排序在这个场景下能跑出接近 O(n) 的表现。课件里专门提了一句“insertion sort is a great algorithm when the data has previously been ordered, but slightly messed up”这句话值得记住。4. 冒泡排序与选择排序两种简单算法背后的设计差异4.1 冒泡排序相邻交换让最小元素逐步上浮冒泡排序的思路在课件里被描述成“双层循环 相邻交换”。外层循环控制第几轮扫描内层循环从数组底部向上遍历每次比较相邻两个元素如果下面更高索引的元素比上面更低索引的元素小就交换它们。这样一轮扫描结束后当前未排序区里最小的元素就“冒泡”到了数组开头按课件里从小到大排序的约定。一个关键优化是每完成一轮扫描已排序区域就增长一位下一轮内层循环不需要再访问它。也就是说第 k 轮扫描只需要处理前 n-k 个元素。课件里明确写了因为第一轮后最小值已经到达顶部第二轮不需要再比较最顶部的两个元素。这个优化在代码里表现为内层循环的边界不断收缩。我给出一个常见实现同时加上一个改进标志def bubble_sort(arr): n len(arr) for i in range(n): swapped False # 本轮是否发生过交换 for j in range(n - 1, i, -1): # 从底部向上扫描 if arr[j] arr[j - 1]: # 相邻元素反序则交换 arr[j], arr[j - 1] arr[j - 1], arr[j] swapped True if not swapped: # 本轮无交换说明已有序 break return arr这里的swapped标志是一个常见优化。如果某一轮完整扫描下来没有任何交换发生说明数组已经有序可以提前终止不需要继续执行外层循环。对原本就有序的数组这个优化让冒泡排序的最好复杂度变成 O(n)和插入排序打了平手。range(n - 1, i, -1)的写法是从最后一个元素开始一直扫描到索引 i 的位置。因为前 i 轮已经把前 i 个最小元素放到了正确位置它们不需要再参与比较。这个边界收缩逻辑是理解冒泡排序的关键也直接决定了总比较次数是 n(n-1)/2 的级别复杂度稳定在 O(n²)。有一种常见的“伪冒泡排序”写法是内层for j in range(n-1-i)每次比较相邻两个并让较大元素往后跑。这种写法方向相反把最大元素移到末尾但本质上和课件的思路一致。区别只在于课件里让最小元素上浮到数组前端而那种写法让最大元素下沉到末尾两者代码镜像但复杂度相同。4.2 选择排序每一轮只做一次有效交换选择排序的思路在三种简单算法里最直观每轮从未排序部分里找到最小元素然后把它交换到未排序部分的起始位置。这个“起始位置”随着排序进行不断后移直到所有元素排完。和冒泡排序相比选择排序的显著特点是比较次数和交换次数分离。无论输入数据是否有序比较次数始终是 n(n-1)/2不会因为数据状态而改变但交换次数最多只有 n-1 次每轮最多交换一次。这在记录体积很大、交换代价远高于比较代价的场景下很有意义。实现如下def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i # 记录最小元素的下标 for j in range(i 1, n): # 扫描未排序区找最小元素 if arr[j] arr[min_idx]: min_idx j if min_idx ! i: # 只在需要时交换 arr[i], arr[min_idx] arr[min_idx], arr[i] return arrmin_idx是这段代码的核心变量它记录的是“最小元素的下标”而不是“最小元素的值”。很多人写选择排序时习惯用一个临时变量存最小值但这样交换时还需要额外记住位置不如直接存下标干净。内层循环结束后min_idx要么还是 i说明当前位置已经是剩余元素中最小的要么指向了更小的元素此时交换一次即可。这个算法还有一个值得注意的性质它不稳定。假设数组是[5a, 3, 5b]其中两个 5 用 a、b 区分第一轮找到的最小值是 3直接和索引 0 位置的 5a 交换结果是[3, 5b, 5a]——两个相同键值 5 的相对顺序从 a 在前变成了 b 在前。这就是选择排序不稳定的原因它跨越了大量元素做远距离交换把相等元素的相对位置破坏了。4.3 三种简单排序的横向对比与选型建议三种算法都教了但实际用哪个要按场景说话。我把课件和实际工程经验里的关键差异整理成一张对比表算法最好复杂度平均复杂度最坏复杂度稳定性交换次数插入排序O(n)O(n²)O(n²)稳定等于移动次数冒泡排序O(n)加优化标志O(n²)O(n²)稳定O(n²)选择排序O(n²)O(n²)O(n²)不稳定O(n)从这张表能读出几件事。第一插入排序在数据“几乎有序”时是绝对赢家这是它在工程上仍然有存在价值的根本原因很多高级排序算法比如 Timsort在数据片段接近有序时会退化成插入排序逻辑。第二选择排序虽然比较次数固定但交换次数最少如果排序的是大对象、交换操作非常昂贵它反而可能比冒泡更实用。第三冒泡排序的定位更像教学工具它把“逆序对交换直到没有逆序对”这个概念展示得最直观但实际应用中几乎没有优势唯一口碑好的变体是针对“大部分已有序”数据的改进版本。课件在“How do you sort”一节里还提到了五种算法思想插入、交换、选择、分布和归并。前三种正好对应这一讲的三个算法而后两种是后续更高级排序算法的基础。这意味着这一讲不只是教三个具体的算法而是让你建立“排序算法的不同设计思路”。5. 排序算法避坑指南课件没直接说的四个典型问题5.1 把稳定性的判断标准记反现象做题时问“冒泡排序是否稳定”回答不稳定问“选择排序是否稳定”回答稳定。原因对稳定性的定义停留在“相同元素不交换”的模糊印象上。冒泡排序相邻交换只发生在逆序时相等元素不会交换所以稳定选择排序发生的是远距离交换很容易把相等元素的位置打乱所以不稳定。这个结论和很多人的直觉相反。解决用一个小例子手推一遍。数组[2a, 1, 2b]按升序排。选择排序第一轮找到最小值 1和 2a 交换结果变成[1, 2b, 2a]相等元素 2 的相对顺序反转了所以不稳定。每次遇到判断稳定性问题都手动推一个带相等键值的例子比死记结论靠谱。5.2 插入排序的移动方向写反现象自己实现插入排序时数组越界或者排序结果里出现重复元素。原因从前往后扫描找插入位置然后从插入点开始往后移动元素结果把还没处理过的元素覆盖了。插入排序必须先从未处理元素的当前位置从后往前比较边比较边移动才能保证不会覆盖后面的未排序数据。解决严格按照“暂存当前元素 → 从后往前扫描 → 边扫描边后移 → 在空位插入”这个顺序来写。我自己的习惯是先在纸上画出第 i 次插入前和插入后的数组状态再写代码基本不会出错。插入排序的移动方向和扫描方向永远是从后往前这一点没有例外。5.3 冒泡排序每一轮的范围没有收缩现象代码能排对但是效率非常低即使数据已经有序也要跑满两层循环。原因没有在每轮扫描后把已排序区域排除在外。比如外层第 i 轮结束后已经有 i 个最小元素位于数组前 i 个位置但内层循环仍然扫描整个数组导致大量无意义的重复比较。解决内层循环的右边界或左边界取决于扫描方向每轮必须收缩。课件里明确提到底部边界会逐步上移代码里体现为range(n - 1, i, -1)这样的区间控制。另外别忘了swapped提前终止标志它能让最好情形的复杂度从 O(n²) 降为 O(n)这个优化在数据接近有序时收益非常明显。5.4 忽略比较器的对称性和传递性现象自定义对象排序时比较函数在某些边界情况下返回结果自相矛盾排序结果不稳定甚至抛异常。原因比较器没有严格遵循排序的数学性质。比如只比较了一个字段但两个对象该字段相等时返回了“等于”而其他字段不同导致算法认为它们“相等”并保持相对顺序或者比较逻辑没有传递性出现 a 大于 b、b 大于 c、但 c 又大于 a 的循环。解决课件里强调的比较函数就是干这个的。在写比较器时先明确三个返回值对应的语义负数表示 a 应排在 b 前面零表示两者“等价”正数表示 a 应排在 b 后面。并且对于相等的情况如果还需要按次要键排序那就把次要键的比较结果作为返回值的一部分而不是直接返回零。这条规则在数据分析和数据挖掘的排序预处理中特别重要因为原始数据里经常出现主键相同、需要依赖次键决定顺序的记录。6. 验证方法把课件里的三种排序跑成对照组课件写得再好不自己动手跑一遍体会始终停留在“看懂”层面。我的建议是把三种排序写成同一个风格的三组函数用同一组随机数据、同一组近乎有序的数据、同一组完全逆序的数据分别跑记录比较次数和运行时间这样复杂度分析就不再是纸面功夫了。给你一个可直接运行的 Python 验证框架思路import random import time def insertion_sort(arr): n len(arr) comp 0 for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: comp 1 arr[j 1] arr[j] j - 1 comp 1 if j 0 else 0 arr[j 1] key return comp def bubble_sort(arr): n len(arr) comp 0 for i in range(n): swapped False for j in range(n - 1, i, -1): comp 1 if arr[j] arr[j - 1]: arr[j], arr[j - 1] arr[j - 1], arr[j] swapped True if not swapped: break return comp def selection_sort(arr): n len(arr) comp 0 for i in range(n - 1): min_idx i for j in range(i 1, n): comp 1 if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return comp # 三组测试数据 random_data [random.randint(0, 1000) for _ in range(500)] sorted_data sorted(random_data) reversed_data sorted(random_data, reverseTrue) for name, func in [(insertion, insertion_sort), (bubble, bubble_sort), (selection, selection_sort)]: for kind, data in [(random, random_data[:]), (sorted, sorted_data[:]), (reverse, reversed_data[:])]: t0 time.time() cnt func(data) print(f{name}-{kind}: comp{cnt}, time{time.time()-t0:.5f}s)这个验证能直接看到三个结论一是选择排序的比较次数在三种数据形态下几乎不变二是插入排序在近乎有序数列上的比较次数会大幅下降三是冒泡排序在不加优化标志时三种数据形态的比较次数都会接近满值。建议你运行之后把每组输出的比较次数记录下来和课件里的复杂度公式做对比你会发现n(n-1)/2和n(n-1)/4这些系数会真实出现在输出结果里。排序这一课是当初我学数据结构时第一份需要完整推演复杂度的材料。从那以后我每学一个新算法都坚持做两个动作先用极小的数据量比如 5 个元素手推每一步再写代码统计比较次数验证理论值。这套习惯帮我避开了大量“貌似懂了、一写就错”的坑也让我养成了拿到数据先看一眼分布特性再决定排序策略的直觉。这份课件如果你耐心看完再把我上面的验证思路跑一遍基础会打得非常扎实。希望帮到你。本文还有配套的精品资源点击获取