大学数据结构《查找与排序》教学课件

数据结构·查找与排序查找·排序·复杂度2026年课程导览01查找基础概念与性能度量02查找算法顺序、二分与哈希03排序入门冒泡排序思想04排序进阶快速与堆排序05综合对比复杂度与选型01查找基础从“找得到”到“找得快”什么是查找与查找表查找是在数据元素集合中确定与给定值相等元素位置的过程—概念起点三要素是掌握后续所有查找算法的前提三个基本要素掌握后续算法的基础查找表存放数据元素的集合，可用数组、链表或树组织关键字标识数据元素，是查找依据查找操作成功查找与失败查找两种结果平均查找长度衡量查找效率ASL为不同查找算法提供了可对比的量化基准。ASL=Σpi

×cipi：查找第i个记录的概率，等概率时为

1/nci：找到第i个记录所需的比较次数含义：查找成功时，与关键字比较的期望次数以顺序查找为例目标在第

1

位比较

1

次目标在第

n

位比较

n

次等概率下ASL(n+1)/2等概率pi=1/n静态查找与动态查找VS这一分类直接决定算法选择：顺序查找与二分查找更适合静态或有序数据；二叉搜索树、哈希表等结构天然支持动态操作。明确场景的静态与动态属性，是算法选型的第一个判断依据。静态查找静：查找期间数据集合不变，无插入、无删除。典型场景成绩表词库一次排序后不再变动的数据。动态查找动：查找的同时允许插入与删除。典型场景通讯录数据库记录随时增删的数据集合。大O表示法的推导规则大O只描述增长趋势，不关心具体运行秒数。化简一个函数时，只需保留增长最快的那一项。三条推导规则常数项用

1

取代低阶项只保留最高阶系数去除最高阶项的系数化简示例n²+3n+5O(n²)常数项5与低阶项3n在n很大时成为次要因素。掌握这套规则，后续每次复杂度结论都能回溯到推导依据。常见复杂度O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)<O(n!)从左到右，增长速度依次升高。02查找算法从逐个比较到直接定位顺序查找的逐个比较核心思想：从一端开始逐个比较关键字，相等即成功，遍历完未找到即失败。适用与代价4项适用场景无需预先有序，顺序表、链表均可，实现简单最好情况比较

1次，O(1)最坏与平均约遍历一半元素，O(n)平均查找长度成功时ASL=(n+1)/2结论：只适合小数据量或少量查询场景。二分查找的折半排除以预处理换查找效率核心机制取有序数组中间值与目标比较，每次排除一半，递归缩小范围。两个硬前提必须满足数据必须已排序必须支持随机访问的顺序存储链表无法直接使用效率对比大幅优势时间复杂度

O(log₂n)对数级增长100万条数据顺序查找平均约

50万次比较，二分查找仅约

20次主要局限不适合频繁插入删除的动态数据集，维护有序性成本高。哈希查找的直接定位核心机制：哈希函数

H(key)

把关键字直接映射为数组下标，查找时只需计算一次哈希值即可定位，平均时间复杂度

O(1)。以哈希换取

O(1)

平均查找，以预处理换查找效率。一次命中示例H(key)=keymod7关键字

28→哈希值

0直接存入下标

0

处冲突与解决不同关键字可能映射到同一位置，需用链地址法或开放定址法处理应用落地哈希表凭借查找、插入、删除的高效率，广泛用于数据库索引与缓存系统Python字典、JavaHashMap

底层均为哈希表树表查找与分块查找树表查找平衡时效率O(logn)插入不当退化链表效率降至O(n)衍生自平衡结构AVL树、红黑树等保障性能二叉搜索树分块查找块间索引定位索引表快速确定所在块块内顺序查找块内逐项比较，线性扫描介于顺序与二分之间方案补全补全动态有序数据查找方案补全中等规模分块数据查找方案两类结构查找算法横向对比场景决定选择，而非复杂度单独决定。复杂度排序哈希查找：O(1)最快二分查找：平均O(logn)平衡树表：平均O(logn)顺序查找：O(n)对数效率数据少且无序选择顺序查找：胜在简单数据多且静态有序选择二分查找：对数效率数据频繁变动红黑树等平衡结构：保障稳定追求极致速度哈希表：几乎无可替代稳定极致03排序入门从相邻交换理解排序排序的分类与基本概念排序：将无序记录按关键字递增或递减排列按存储位置分两类内存·外存内部排序：全过程在内存中完成外部排序：数据量大，需借助外存稳定性相等关键字稳定：排序后相等关键字的相对位置保持不变不稳定：相对位置改变稳定性的价值多关键字排序先按次要关键字、再按主要关键字排序，稳定算法能保留前一轮的有序结果。稳定性是理解后续每个排序算法的共同标尺冒泡排序的相邻交换从左到右逐对比较相邻元素，左边大于右边就交换。核心逻辑第1环逐对比较从左到右逐对比较相邻元素，左边大于右边就交换。一轮结束第2环冒泡归位一轮结束，最大元素像气泡被“顶”到最右端；对剩余元素重复，共

n-1

轮后整体有序。数据演示第3环示例序列以

49、38、65、97、76、13、27、1

为例：第1轮

97归位，第2轮

76归位，依此类推，逐轮归位。特点小结第4环教学首选逻辑直观、代码易懂，排序教学首选入门案例，适合小数据量与课堂演示。冒泡排序的优化与复杂度算法思想冒泡排序：两两比较相邻元素每轮冒泡：最大元素浮至末尾n-1轮：序列整体有序优化机制提前结束：一趟扫描无交换即有序最优情形：正序数据一轮完成复杂度分析最好数据正序，一轮扫描确认无交换O(n)最坏数据反序，完整n-1轮比较O(n²)平均综合所有输入情形O(n²)空间与稳定性空间复杂度

O(1)仅借一个临时变量完成交换稳定排序相等元素不发生交换，相对位置保持不变插入排序与选择排序插入排序与选择排序同为O(n²)级算法，核心价值是建立排序直觉，为高效进阶算法做铺垫。两种最直观的排序算法：插入排序像理牌，选择排序像挑最小——先建立直觉，再谈效率。三者同为

O(n²)

级算法，核心价值是建立排序直觉，为高效进阶算法做铺垫。插入排序像打扑克每摸一张新牌就插入手中合适位置，前段有序、后段待插。从后向前与已排序部分比较，边比较边移动，找到位置后插入。数据基本有序时特别快：最好

O(n)，最坏

O(n²)。选择排序挑最小的放最前每轮从未排序区间选出最小元素，放到已排序区间末尾。每轮最多交换一次，比较次数固定为

n(n-1)/2。恒为

O(n²)，且不稳定。04排序进阶从分治与堆结构提升效率快速排序的分治思想一趟定一位PARTITION选基准值

pivot，左边

≤pivot，右边

≥pivot，基准位置唯一确定。递归折半DIVIDE&CONQUER对左右子序列重复划分，直到每部分只剩一个元素。效率跃升SPEEDUP冒泡每趟只归位一个元素；快速排序一趟归位一个元素，同时把问题规模折半。工程地位INDUSTRYSTANDARD大多数编程语言的内置排序函数底层都采用快速排序或其变种。快速排序的复杂度与稳定性实际表现由基准选取策略与数据分布共同决定。平均与最坏分化平均：划分均衡，递归深度约

log₂n

层，时间复杂度

O(nlogn)最坏：数据已有序且固定选首元素为基准，每次只排除一个元素，递归退化为n层，时间复杂度恶化到

O(n²)维空间与稳定性空间空间复杂度来自递归调用栈，平均为

O(logn)稳定快速排序是不稳定排序，相等元素在划分过程中相对位置可能改变堆排序的建堆与取顶最大堆：完全二叉树，任意节点值不小于其子节点。堆排序三步流程01建堆无序序列构建为最大堆，堆顶即全序列最大元素02取顶取出堆顶，放到当前未排序区间末尾03归位末尾元素换到堆顶，向下调整重建最大堆升序示例↳首轮堆顶

97

归位至最后↳次轮76

归位至倒数第二↳依次依此类推，至排序完成堆排序的复杂度与应用复杂度稳定复杂度分析时间复杂度恒为

O(nlogn)，不随数据分布退化。原地排序，空间复杂度仅

O(1)，适合内存敏感场景。代价与短板局限性分析不稳定排序。数据访问方式对

CPU缓存不友好，实际运行通常略慢于快速排序。TopK场景的独特价值应用场景从

100万个数据中找最大的

10个，无需全量排序。维护一个大小为

10的小根堆即可高效完成——这是快速排序难以匹敌的。归并排序的稳定合并先拆后合——将大问题分解成可独立求解的子问题➜➜以空间换稳定与确定性1步骤01先拆后合递归拆分数组对半拆分，直到每个子数组只剩一个元素单个元素天然有序2步骤02两两合并比较合并比较两个有序子数组的头部元素谁小谁先输出，直到合并完成3步骤03稳定与代价权衡分析稳定：适合多关键字排序复杂度：保持

O(nlogn)空间：需辅助数组，O(n)05综合对比从复杂度看算法选型复杂度的直观数量感同一规模，数量级天差地别复杂度阶梯每一次跃升，背后都是数量级的质变。同一规模，数量级天差地别n=10⁶O(logn)≈20次O(n)=10⁶次O(nlogn)≈2×10⁷次O(n²)=10¹²次复杂度阶梯每一次跃升，背后都是数量级的质变百万规模下二分查找

20次比较即可完成，暴力双层循环已到无法在有限时间完成的量级。题目数据规模10⁴～10⁵时O(n²)通常超时，O(nlogn)及以下才能顺利通过。排序算法综合对比两条效率分界线平方级：冒泡、插入、选择——平均O(n²)，适合小规模数据线性对数级：快速、归并、堆——平均O(nlogn)，大规模主流选择算法最好平均最坏空间稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定插入排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定选型权衡：稳定性与空间是平方级之外的第二层考量——归并稳定但需O(n)额外空间，堆排序O(1)空间却不稳定。查找算法综合对比算法平均时间复杂度前提条件适用场景顺序查找O(n)无需有序小数据·无序二分查找O(logn)必须有序且顺序存储静态有序数组二叉搜索树O(logn)保持平衡频繁动态变动分块查找介于两者之间分块+索引中等规模哈希查找O(1)构造哈希函数追求极致速度复杂度优势，必须