简介这份英文教学课件面向计算机专业学生与算法入门者系统讲解数据结构中排序这一核心主题帮助读者建立对基础排序算法的完整认知。课件指出排序是最基础的算法问题约25%的CPU运算周期消耗于此并强调其对二分查找等后续算法的支撑作用。内容涵盖排序基本概念、比较器与关键字、稳定性定义以及内部排序与外部排序的区分并重点剖析插入排序、冒泡排序、选择排序三种简单算法的原理与时间复杂度同时讨论升序降序、相等键值处理、非数值数据排序等实际问题。资源包为1个PDF文件约449KB篇幅精炼适合课堂配套或自学查阅。目前已有114人学习下载。读者可借此掌握三种基础排序的实现思路与性能差异理解排序在大数据分析与数据挖掘中的效率意义为后续复杂算法设计与优化打下基础。1. 从一份英文课件说起22_sorting_01.pdf 到底能解决什么如果你正在准备数据结构期末、考研 408或者带本科生的算法课手里大概率会缺一份能把「排序」这件事从概念到复杂度讲透的英文讲义。这份22_sorting_01.pdf就是重庆大学计算机学院数据结构课程里 Sorting 部分的第一讲全英文覆盖排序的基本定义、术语约定、应用场景以及插入排序、冒泡排序、选择排序三种简单算法的原理、实现思路和复杂度推导。它不只是一份 PPT 转出来的课件而是把「为什么排序值得单独开一讲」讲清楚了——课件里直接给了一个数字大约 25% 的 CPU 周期花在排序上。这个数字放在大数据和数据挖掘的语境里看意味着排序效率直接决定了下游二分查找、去重、频率统计、中位数选择这些操作的可行性。适合谁适合需要一份结构完整、术语规范、复杂度推导有过程的教学材料的人也适合想用英文原始表述对照中文教材查漏补缺的读者。2. 排序的基本概念与术语先立住比较函数和稳定性2.1 排序问题的形式化定义课件对排序的定义很干脆给定 n 个元素的任意排列把它们重新排成满足全序关系的结果。用数学语言写就是对于任意 i j排序后满足 X_i ≤ X_j。这个定义看起来简单但它隐含了一个前提——元素之间必须存在一个可比较的关系。课件里把这个关系交给一个 comparator class 来处理每条记录有一个 key field比较器从记录里把 key 抽出来做比较。这个设计思路在实际工程里非常常见比如 Java 的Comparator接口、Python 的key参数、C 的std::sort自定义比较函数本质上都是同一件事把「怎么比」和「怎么排」解耦。为什么要把比较函数单独拎出来讲因为排序算法本身不关心你比的是整数、字符串还是自定义对象它只关心比较函数返回的是小于、大于还是等于。课件里明确写了Compare(a, b) 应该返回、或。这意味着你换一种数据类型只要比较函数写对排序算法不用改一行。这也是为什么后面讲插入排序、冒泡排序、选择排序时课件始终用「key」而不是「数字」来描述。2.2 稳定性、内部排序与外部排序课件里对稳定性的定义值得逐字读如果一个排序算法不改变具有相同 key 值的记录的相对顺序那它就是稳定的。注意这里说的是「相对顺序」不是「位置」。举个例子你有一组学生记录先按姓名排过一遍现在要按班级排如果排序算法是稳定的同一个班里的学生仍然保持姓名有序如果不稳定姓名顺序就乱了。这个性质在多级排序里非常关键比如 SQL 里的ORDER BY class, name底层实现如果用了不稳定的排序算法就必须额外处理才能保证结果正确。课件还区分了内部排序和外部排序。内部排序是数据全部能放进内存外部排序是数据量大到必须借助磁盘分块处理。这个区分在大数据场景下尤其重要因为 MapReduce 的排序阶段本质上就是外部排序——数据先分片每个分片内部排序再归并。课件虽然只讲了三种简单排序但把内部/外部的边界先划清楚了后面学归并排序和快速排序时就不会混淆适用场景。2.3 排序的四个典型应用课件列了四个应用场景每一个都值得展开看二分查找排序之后查找一个元素的时间从 O(n) 降到 O(log₂ n)。这是排序最直接的价值也是课件里说的「加速查找可能是排序最重要的应用」。最近点对给定 n 个数找差值最小的那一对。排序之后最近的一对必然相邻一次 O(n) 线性扫描就能搞定。元素唯一性判断一组元素里有没有重复。排序后扫描相邻元素即可本质上是最近点对的特例。频率分布与中位数排序后扫描相邻的连续段就能统计众数第 k 大的元素直接看数组第 k 个位置O(1) 时间。这四个场景的共同逻辑是排序把「全局比较」变成了「局部比较」。一旦数据有序很多看起来需要两两比较的问题都退化成相邻元素的检查。这也是为什么课件反复强调排序是「最基础的算法问题」。3. 三种简单排序的实操拆解插入、冒泡、选择3.1 插入排序从打牌到数组搬移课件对插入排序的引入很直观——整理扑克牌。你从左到右摸牌每摸一张就把它插到手里已经排好的牌的正确位置。插入排序的核心操作是遍历列表每处理一条记录就把它插入到已排序部分的正确位置。课件特别区分了数组和链表两种存储方式下的插入代价。数组里插入一个元素需要从插入位置到末尾的所有元素往后挪一位链表里插入只需要找到位置后改指针不需要搬移其他元素。这个区别在实际写代码时很关键因为数组的搬移操作是 O(n) 的而链表的插入本身是 O(1)但链表的顺序查找仍然是 O(n)。用 Python 写一个数组版的插入排序def insertion_sort(arr): # 从第二个元素开始逐个插入到前面已排序的部分 for i in range(1, len(arr)): key arr[i] # 当前要插入的元素 j i - 1 # 从右往左扫描已排序部分找到 key 应该放的位置 while j 0 and arr[j] key: arr[j 1] arr[j] # 比 key 大的元素往后挪 j - 1 arr[j 1] key # 把 key 放到正确位置 return arr这段代码里key是当前待插入的记录j从i-1开始往左扫描。while循环的条件arr[j] key决定了排序是升序还是降序——如果你想降序把改成就行。循环体里arr[j1] arr[j]就是课件说的「搬移元素」每搬一次就是一次数据移动。最后arr[j1] key把待插入元素放到空出来的位置。复杂度方面课件给了三种情况情况比较次数移动次数时间复杂度最好已有序n-10O(n)最坏逆序n(n-1)/2n(n-1)/2O(n²)平均n(n-1)/4n(n-1)/4O(n²)最好情况是数组已经有序每次插入只需要和最后一个元素比一次不用搬移。最坏情况是逆序第 i 次插入需要比较 i-1 次、搬移 i-1 次。平均情况课件推导了期望比较次数第 i 次插入需要 0 到 i-1 次比较的概率相等期望是 (i-1)/2累加后是 n(n-1)/4正好是最坏情况的一半。这个推导过程在课件里有完整步骤值得对着看一遍。3.2 冒泡排序双重循环与提前终止冒泡排序的结构是双重 for 循环。内层循环从下往上扫描比较相邻的两个 key如果下面的比上面的大就交换。每一轮内层循环结束后当前未排序部分里最小的元素会「冒」到顶端。课件特别提到一个优化点第一轮结束后最小的元素已经在顶端了第二轮就不需要再比较最上面两个元素。用 Python 实现def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False # 每一轮把未排序部分的最小值冒到位置 i for j in range(n - 1, i, -1): if arr[j - 1] arr[j]: arr[j - 1], arr[j] arr[j], arr[j - 1] swapped True # 如果这一轮没有发生任何交换说明已经有序 if not swapped: break return arr外层循环控制轮数最多 n-1 轮。内层循环从n-1递减到i1比较arr[j-1]和arr[j]。注意这里是从后往前扫所以最小的元素会往索引小的方向移动。swapped标志位是一个提前终止的优化如果某一轮没有任何交换说明数组已经有序直接跳出。这个优化在数据接近有序时能把最好情况降到 O(n)。冒泡排序的比较次数在最坏情况下和插入排序一样是 n(n-1)/2但交换次数更多因为每次交换涉及三个赋值操作。实际工程里冒泡排序很少用但它的教学价值在于它是「交换」这一类排序思路的最简单代表理解了冒泡再学快速排序的分区交换就顺了。3.3 选择排序找最小值和交换位置选择排序的思路是每次从未排序部分里找出最小的元素把它和未排序部分的第一个元素交换。课件里的描述是「extract the largest element from the list, remove it, and repeat」这是从大到小排的版本从小到大排就是每次找最小。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 arr外层循环i从 0 到 n-2表示已排序部分的边界。内层循环在i1到n-1里找最小值的索引min_idx。找到之后如果min_idx不等于i就交换。选择排序的比较次数固定是 n(n-1)/2不管数据初始状态如何因为每一轮都必须扫描完整个未排序部分才能确定最小值。但交换次数最多只有 n-1 次这是它比冒泡排序好的地方——如果记录很大、移动成本高选择排序的交换次数少反而有优势。三种简单排序的对比算法最好时间最坏时间平均时间空间稳定性插入排序O(n)O(n²)O(n²)O(1)稳定冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定选择排序不稳定的原因假设数组是[2a, 2b, 1]第一轮找到最小值 1和第一个位置的 2a 交换得到[1, 2b, 2a]两个 2 的相对顺序变了。插入排序和冒泡排序在遇到相等元素时不交换所以稳定。4. 避坑与排查三种简单排序里最容易翻车的五个点4.1 边界条件写错导致数组越界现象插入排序的while循环里忘了写j 0当key比前面所有元素都小时j会减到 -1下一轮访问arr[-1]在 Python 里不会报错但逻辑错了在 C/Java 里直接越界崩溃。原因插入排序的内层循环是从右往左扫描循环变量递减终止条件必须同时检查下标有效性和比较结果。解决把j 0放在and的左边利用短路求值避免越界。写完之后用[5,4,3,2,1]和[1,2,3,4,5]各跑一遍确认两端边界都覆盖到。4.2 稳定性被破坏却不自知现象用选择排序对一组学生记录按成绩排序成绩相同的学生姓名顺序变了导致后续按姓名分组时结果错乱。原因选择排序在交换最小值时可能把前面已经排好的相同 key 的记录换到后面去破坏了相对顺序。解决如果业务要求稳定选择排序不能直接用。要么换成插入排序或冒泡排序要么在比较函数里加入次要 key比如成绩相同时比姓名把不稳定的问题转化成全序比较。4.3 把「比较次数」当成「运行时间」现象课件里说插入排序平均比较次数是 n(n-1)/4有人就认为它比选择排序快一倍实际跑起来发现差距没那么大甚至更慢。原因比较次数只是运行时间的一个因素数据移动的次数和代价同样重要。插入排序在数组里每次插入都要搬移元素而选择排序每轮只交换一次。如果记录很大搬移成本远高于比较成本。解决分析排序算法时同时看比较次数和移动次数。课件里专门提了「the number of swap operations」作为另一个衡量指标就是这个原因。实际选型时如果记录很大优先考虑移动次数少的算法或者用索引排序——只排索引数组不搬移原始记录。4.4 冒泡排序的提前终止条件写反现象加了swapped标志位之后排序结果不对或者提前终止导致数据没排完。原因swapped应该在每一轮内层循环开始时重置为False如果放在外层循环外面第一轮之后永远是True提前终止就失效了。解决swapped False必须放在外层循环体内、内层循环之前。每轮内层循环结束后检查swapped如果为False才break。4.5 对「逆序数组冒泡排序是 O(n)」的误解现象有人说冒泡排序在逆序数组上能达到线性时间因为每轮都能把元素放到最终位置。原因这是把「交换次数」和「比较次数」搞混了。逆序数组上冒泡排序每一轮仍然要比较所有相邻对比较次数是 n(n-1)/2不可能降到 O(n)。课件里说的「某些特定情况下可以达到线性时间」指的是最好情况——数组已经有序加上提前终止优化只需要 n-1 次比较。解决记住冒泡排序的最好情况是「已有序 提前终止」不是「逆序」。逆序是最坏情况比较和交换都是 O(n²)。5. 从课件到落地用复杂度推导反推算法选型5.1 用课件里的推导方法验证一个排序实现课件对插入排序平均情况的推导值得单独拿出来练一遍因为这套方法可以迁移到其他算法的分析上。推导的逻辑是第 i 次插入时待插入元素在已排序部分里的最终位置有 i 种可能从最前面到最后面每种位置需要的比较次数分别是 1, 2, ..., i-1, i-1概率相等所以期望比较次数是 (i-1)/2。累加 i 从 1 到 n得到 n(n-1)/4。你可以用这个思路验证冒泡排序的平均比较次数。冒泡排序每一轮内层循环的比较次数是固定的第 i 轮比较 n-i 次总比较次数是 n(n-1)/2和初始状态无关。但交换次数和初始状态有关平均交换次数也是 n(n-1)/4。这个推导过程能帮你理解为什么冒泡排序的平均时间复杂度和插入排序一样是 O(n²)但实际运行中插入排序通常更快——因为插入排序的比较次数在数据部分有序时会减少而冒泡排序的比较次数是固定的。5.2 什么场景下这三种简单排序仍然值得用虽然这三种算法的时间复杂度都是 O(n²)但在以下场景里它们仍然有实用价值数据量很小n 50O(n²) 和 O(n log n) 的差距在 n 很小时可以忽略插入排序的常数因子小实际可能更快。数据接近有序插入排序在这种场景下接近 O(n)是三种算法里最快的。内存极度受限三种算法都是原地排序空间 O(1)不需要额外分配内存。需要稳定排序且不想引入额外依赖插入排序和冒泡排序是稳定的实现简单适合嵌入式或脚本场景。作为混合排序的子过程很多标准库的排序实现会在小数组上切换到插入排序比如 Java 的Arrays.sort在数组长度小于 47 时用插入排序。5.3 一个具体的验证方法用逆序对数量预估插入排序的移动次数插入排序的移动次数等于数组中逆序对的数量。逆序对的定义是 i j 但 arr[i] arr[j] 的数对。你可以在排序前用 O(n²) 的暴力方法统计逆序对数量然后和插入排序实际执行的移动次数对比验证两者是否一致。def count_inversions(arr): # 暴力统计逆序对数量用于验证插入排序的移动次数 count 0 for i in range(len(arr)): for j in range(i 1, len(arr)): if arr[i] arr[j]: count 1 return count def insertion_sort_with_count(arr): moves 0 for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] moves 1 j - 1 arr[j 1] key return arr, moves # 测试 test [5, 3, 8, 1, 9, 2] inv count_inversions(test) sorted_arr, moves insertion_sort_with_count(test[:]) print(f逆序对数量: {inv}, 插入排序移动次数: {moves}) # 输出应该两者相等这段代码里count_inversions用双重循环统计所有逆序对时间复杂度 O(n²)。insertion_sort_with_count在插入排序的基础上加了一个moves计数器每次执行arr[j1] arr[j]时加一。运行结果会显示逆序对数量和移动次数完全相等因为插入排序每消除一个逆序对恰好对应一次元素搬移。这个验证方法能帮你确认自己对插入排序执行过程的理解是否准确。从那以后我每次拿到一份新的排序课件或教材都会先挑一个算法用逆序对数量去对一遍它的移动次数对不上就说明我对这个算法的理解有偏差。这个习惯帮我省了很多「以为自己懂了其实没懂」的时间。希望帮到你。本文还有配套的精品资源点击获取