这一篇不再详细讲过程重点解决408选择题复杂度、稳定性、空间、初始状态影响、适用场景、外部排序。一、先看408最重要总表排序算法最好平均最坏空间稳定性直接插入O(n)O(n²)O(n²)O(1)稳定折半插入O(n²)*O(n²)O(n²)O(1)稳定希尔与增量有关与增量有关可到O(n²)O(1)不稳定冒泡O(n)O(n²)O(n²)O(1)稳定快速O(n log n)O(n log n)O(n²)O(log n)平均不稳定简单选择O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定二路归并O(n log n)O(n log n)O(n log n)O(n)稳定基数O(d(nr))同左同左O(nr)稳定说明折半插入虽然比较次数可降到O(n log n) 但元素移动仍可能O(n²)所以整体仍是O(n²)。二、稳定性秒杀表稳定直接插入 折半插入 冒泡 归并 基数不稳定希尔 快速 简单选择 堆可以记成稳定插冒归基 不稳定希快选堆其中“插”包括直接插入 折半插入三、哪些算法最受初始序列影响直接插入非常受影响。基本有序 - 很快 O(n) 逆序 - O(n²)冒泡也受影响。带提前结束标志时已经有序 - O(n)快速排序非常受pivot和初始序列影响。如果固定选首元素基本有序 / 逆序 - 可能退化到O(n²)简单选择几乎不受初始序列影响。因为每趟都必须扫描整个未排序区间找最小比较次数始终n(n-1)/2堆排序、归并排序时间复杂度较稳定都是O(n log n)四、408场景选择秒杀场景1序列基本有序优先直接插入 冒泡带提前结束最典型直接插入场景2n很小优先直接插入原因实现简单 常数小场景3要求稳定可考虑插入 冒泡 归并 基数场景4要求最坏仍O(n log n)优先堆排序 归并排序不要选快速排序。场景5要求额外空间尽量小可考虑堆排序 O(1)归并O(n)空间更大。场景6大量数据在外存优先归并思想即外部排序 - 多路归并场景7链表排序更适合归并排序因为链表不适合随机访问但归并只需要顺序扫描。五、比较排序的下界如果排序算法只通过比较关键字大小来确定顺序那么平均意义下至少需要Ω(n log n)级别的比较。因此比较排序不可能普遍做到O(n)但基数排序 计数排序 桶排序不完全依赖关键字比较所以可以突破这个限制。六、快排、堆排、归并三大重点横向对比对比快速排序堆排序归并排序平均时间O(n log n)O(n log n)O(n log n)最坏时间O(n²)O(n log n)O(n log n)空间递归栈O(1)O(n)稳定否否是初始序列影响大小小核心操作划分堆调整合并典型优势平均很快最坏稳定、空间小稳定、适合外排408里如果三者放一起比较重点看稳定性 最坏复杂度 空间七、交换次数和比较次数常考结论简单选择排序比较次数n(n-1)/2与初始序列无关。交换次数最多n-1次冒泡排序逆序情况下交换次数最多交换次数等于逆序对数量这是一个很重要的结论。插入排序元素移动量也和逆序对数量高度相关。序列越接近有序插入排序越快八、堆排序的高频计算1. 建大根堆升序时父结点 孩子从最后一个非叶子结点开始向前调整。若n个元素从1开始编号最后一个非叶子结点 floor(n/2)所以建堆时i floor(n/2), ..., 1依次向下调整。2. 每趟输出升序排序堆顶最大把堆顶 - 当前最后元素交换。然后堆大小减1 重新向下调整根九、归并排序的高频计算如果有n个元素每次二路归并归并趟数 ceil(log2 n)例如n 10则ceil(log2 10) 4需要4趟二路归并。每一趟处理全部n个元素因此O(n log n)十、外部排序先理解为什么需要它如果数据太大内存一次装不下就只能磁盘 - 内存反复读写。这叫外部排序外部排序最重要的成本不是CPU比较而是磁盘I/O次数因此目标尽量减少归并趟数十一、外部排序标准流程第一步生成若干初始归并段 第二步对这些归并段进行多路归并 第三步不断归并直到只剩一个有序文件十二、多路归并趟数公式设r 初始归并段数量 k k路归并则归并趟数约为ceil(log_k r)例如16个初始归并段 2路归并需要log2 16 4趟如果改成4路归并则log4 16 2趟所以归并路数越大 归并趟数越少 I/O次数越少十三、败者树是干什么的多路归并时每一轮都要从k个归并段当前元素中找最小值。如果每次普通扫描比较成本较高败者树用于快速从k路中找当前最小元素本质上减少CPU比较次数注意败者树本身不会直接减少归并趟数归并趟数主要取决于初始归并段数量r 归并路数k十四、如何减少外部排序I/O两个最重要方向方法1增大归并路数kk越大 log_k r越小 归并趟数越少方法2减少初始归并段数量r也就是让每个初始归并段更长常见技术置换-选择排序它可以生成比内存容量更长的初始归并段。十五、排序算法“第一反应”表看到题目关键词直接联想基本有序 - 直接插入 每趟最大值到末尾 - 冒泡 pivot归位 - 快速 每趟选最小值 - 简单选择 大根堆/小根堆 - 堆排序 两个有序段合并 - 归并 个位十位百位 - 基数 外存、磁盘I/O - 多路归并十六、稳定性怎么判断判断一个排序是否稳定只看两个关键字相同的元素 排序前后相对顺序会不会被颠倒例如5a 3 5b排序后如果3 5a 5b稳定。如果可能3 5b 5a则不稳定。十七、408选择题最常见陷阱1. 快速排序最快所以任何时候都最好错。最坏O(n²) 不稳定 递归需要额外空间2. 折半插入排序是O(n log n)错。比较少了 移动仍然O(n²)3. 堆排序稳定错。不稳定4. 归并排序空间O(1)错。数组上的二路归并一般需要O(n)辅助空间。5. 简单选择排序在原序列有序时会变快错。比较次数基本不变。6. 希尔排序稳定错。不稳定十八、考前1分钟总表直接插入 稳定O(n²)基本有序最好O(n) 折半插入 稳定比较少整体仍O(n²) 希尔 不稳定原地 冒泡 稳定O(n²)最好O(n) 快速 不稳定平均O(nlogn)最坏O(n²)pivot归位 简单选择 不稳定始终O(n²)比较次数固定 堆 不稳定O(nlogn)O(1)空间 归并 稳定O(nlogn)O(n)空间 基数 稳定非比较排序O(d(nr))十九、强化阶段你最需要练什么排序这一章不建议平均用力。优先级第一档 快速排序 堆排序 归并排序 第二档 直接插入 冒泡 简单选择 第三档 希尔 基数 外部排序每种算法至少练两类题1. 给初始序列问一趟之后结果 2. 给性质判断稳定性/复杂度/适用场景二十、回去复习的位置408数据结构 - 第8章 排序 - 8.1 基本概念 - 插入排序 - 交换排序 - 选择排序 - 归并排序 - 基数排序 - 外部排序 - 排序算法分析与应用最后真正要做到的是看到序列变化 - 认算法 看到场景 - 选算法 看到性质 - 秒判断