数据结构排序算法精讲：插入、冒泡、选择排序与稳定性分析

简介：数据结构英文教学课件聚焦排序（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 次移动。把所有代价加起来：比较总数是 1+2+...+(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 arr

min_idx是这段代码的核心变量，它记录的是“最小元素的下标”而不是“最小元素的值”。很多人写选择排序时习惯用一个临时变量存最小值，但这样交换时还需要额外记住位置，不如直接存下标干净。内层循环结束后，min_idx要么还是 i，说明当前位置已经是剩余元素中最小的；要么指向了更小的元素，此时交换一次即可。

这个算法还有一个值得注意的性质：它不稳定。假设数组是[5a, 3, 5b]，其中两个 5 用 a、b 区分，第一轮找到的最小值是 3，直接和索引 0 位置的 5a 交换，结果是[3, 5b, 5a]——两个相同键值 5 的相对顺序从 a 在前变成了 b 在前。这就是选择排序不稳定的原因：它跨越了大量元素做远距离交换，把相等元素的相对位置破坏了。

4.3 三种简单排序的横向对比与选型建议

三种算法都教了，但实际用哪个要按场景说话。我把课件和实际工程经验里的关键差异整理成一张对比表：

从这张表能读出几件事。第一，插入排序在数据“几乎有序”时是绝对赢家，这是它在工程上仍然有存在价值的根本原因，很多高级排序算法（比如 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, reverse=True) 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 个元素手推每一步，再写代码统计比较次数验证理论值。这套习惯帮我避开了大量“貌似懂了、一写就错”的坑，也让我养成了拿到数据先看一眼分布特性再决定排序策略的直觉。这份课件如果你耐心看完，再把我上面的验证思路跑一遍，基础会打得非常扎实。希望帮到你。

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