第 1 章 绪论知识点数据结构课程主要研究三个方面① 数据的逻辑结构数据元素间的抽象关系如线性、树形数据之间的逻辑关系② 数据的存储结构逻辑结构在计算机中的表示如顺序、链式数据在计算机内存中的实际存储方式③ 定义在该结构上的基本操作算法数据的物理结构顺序存储 链式存储是指数据在计算机内的实际存储形式算法的五大特性有穷性步骤有限确定性每条指令无歧义可行性/可执行性能通过基本运算实现输入0个或多个输出至少1个数据的组成层次数据项最小单位数据元素基本单位数据对象性质相同的数据元素集合示例数据项学号、姓名、年龄数据元素一个学生数据对象全班学生数据结构的三要素逻辑结构数据之间有什么关系存储结构数据在计算机里怎么存数据运算对数据能做什么操作示例线性表逻辑结构一对一存储结构顺序存储或链式存储数据运算插入、删除、查找、遍历题型线性 / 非线性数据结构题型分类逻辑关系代表结构线性结构一对一表 栈 队列 串 数组非线性结构一对多/多对多图 树 广义表 矩阵时间复杂度O (1) 操作按下标读、按下标改随机访问O (n) 操作任意位置插入、任意位置删除、按值遍历查找无论插入 / 删除在表头、表中、表尾复杂度永远 O (n)第 2 章 线性表知识点线性表可以是空表 长度为0线性表第一个元素没有前驱最后一个没有后继顺序表和链表优势类型优势链表顺序读取 频繁插入和删除顺序表通过下标访问 随机读取 查询多 很少增删双链表顺序遍历 O (n)找到节点后可直接取前驱额外存双向指针空间开销大单循环链表遍历逻辑同单链表 O (n)首尾相连仅适合频繁操作表头表尾场景随机存取/顺序存取指存取任何一个元素的时间复杂度都是 O(1)比如数组直接通过下标计算地址指存取某个元素必须从头开始遍历时间复杂度为 O(n)。单链表每个结点都存储了下一个结点的地址要访问第 i 个结点必须从第一个结点开始逐个next指针往后找不能直接计算出第 i 个结点的地址。所以单链表是“顺序存取”结构不是随机存储结构。单链表不是一种随机存储结构随机存储结构是想访问第几个就能直接跳到第几个 显然数组更符合这个规定 所以数组随机存储结构题型线性表存储结构选择题选择按序号访问多随机存取顺序表。尾部插删多顺序表。经常在中间插入删除链表表头插入和删除单链表 / 带头结点链表经常在表尾插入带尾指针的单循环链表经常在表尾插入和删除双循环链表既要找前驱又要找后继双链表需要从任意结点方便前后移动双链表 / 双循环链表双向遍历选双链表。循环访问选循环链表。头尾都频繁选双循环链表。空间最省选顺序表类型结构特点优势劣势常考关键词顺序表用数组连续存储按下标访问快随机存取快表尾插入删除快中间插入删除要移动大量元素长度不易扩展按序号访问、第 i 个元素、随机存取、很少插删、表尾插删单链表每个结点只有next指针插入删除方便表头插删快长度灵活不能随机访问找第 i 个元素要从头遍历找前驱麻烦频繁插入删除、表头插删、不需要随机访问带头结点单链表多一个头结点不存有效数据统一空表和非空表操作表头插删方便仍然不能随机访问找前驱仍麻烦表头插入、表头删除、操作统一单循环链表尾结点next指回头结点从任一结点出发可遍历整个表适合循环处理找前驱仍然麻烦没有尾指针时找尾结点慢循环处理、首尾相接、约瑟夫环带尾指针的单循环链表只设尾指针rear尾结点指向头结点表尾插入快也能快速找到头结点表尾删除仍然要找前驱较慢只在表尾插入删除、队列链式存储双链表每个结点有prior和next找前驱和后继都方便已知结点时插删快空间开销大多一个前驱指针找前驱、找后继、双向遍历、已知结点插删双循环链表双链表首尾相连表头表尾操作都方便尾插尾删都快空间开销更大指针修改较复杂表尾插入和删除、表头表尾都频繁操作带头结点的双循环链表有头结点且双向循环操作最统一表头、表尾插入删除都方便指针域多空间开销最大表尾插入删除、表头插入删除、前驱后继都要快最主要的快例题在设计某图书管理系统的过程中如果需要经常更新书单数据则采用_存储方式效率较高。这个的意思是经常有新书上架插入有旧书下架删除故填链式顺序表插入/删除时元素移动次数问题插入如果顺序表有n个元素现在要插入到第i个位置前面 移动位置n-i1插入位置是n1通过公式S(首项末项)/2×项数​顺序存储结构地址计算公式公式 (Loc(a_i)Loc(a_0)i×L)符号定义Loc(a_i) 对应的是第i个元素的地址即所求地址Loc(a_0) 第0个元素地址即首地址i 对应的是元素对应的这个数组的下表第四个元素的对应下表是3L 每个元素对应的存储空间大小链表指针操作代码题宗旨先连新结点再移动指针尾结点要置空插入先让新结点接后面再让前面接新结点删除先保存要删的结点再让前面跳过它入队尾巴接新结点rear 移到新尾。出队front 跳过队头删最后一个时 rear 回到 front先让新结点接后面再让前面接新结点通用解法链队列入队Q-rear-next s旧尾节点接上新增节点 sQ-rear s尾指针更新指向新尾部s-next NULL队尾无后继置空链队列出队p Q-front-next取出第一个数据节点Q-frontQ-front-next释放/保存p数据普通单链表头插s-next L-nextL-next s第 3 章 栈和队列知识点队列的元素个数(rear - front N) % Nrear frontrear front先算出前后位置的差值如果不够负数就补一圈如果多算了超过一圈就取余数去掉计算机主机与打印机间速度不匹配问题通常设一个打印数据缓冲区 缓冲区的逻辑结构是队列先进先出递归的执行规则后调用 先返回 符合栈的特性队满条件(rear 1) % n front队空条件frontrear题型出栈顺序技巧循环队列的入队标准动作概念front指向队头元素rear指向队尾元素的下一个空闲位置。步骤看数组范围 算总长度如果写的是A[0..m]总长度 m1如果写的是A[1..n]总长度 n确认指针指向谁front指向队头rear指向队尾的下一个空位 入队用rear出队用front套公式入队A[rear] x; rear (rear 1) % 总长度//总长度是入队后的总长度出队:front (front 1) % 总长度;取队头元素是A[front]//总长度是出队后的总长度队列删除/插入指针变化操作指针变化删除 k 个元素front (front k) % m插入 k 个元素rear (rear k) % m队列元素个数(rear - front N) % N思路出队动 front入队动 rear移动后取模超过末尾回到 0栈进出序列判断中缀表达式转后缀表达式优先级运算符优先级等级说明* /2先计算 -1后计算(0遇左括号直接压栈绝不与任何运算符比较插入运算符的时候 看运算符栈栈顶 如果大于运算符栈栈顶 直接将运算符压入栈 否则栈顶不断弹出 直至栈空或栈顶为(解题步骤扫描中缀表达式遇到操作数数字/字母直接输出不犹豫遇到左括号直接压入栈不管优先级遇到右括号)疯狂弹出栈顶运算符并输出直到遇到左括号(左括号弹出丢弃但不输出遇到运算符 - * /等优先级比较前的“豁免权”如果栈为空或者栈顶是左括号(则不做任何优先级比较直接将该运算符压入栈中。正常比较重点修改只有当栈不为空且栈顶不是左括号时才去比较栈顶运算符与当前运算符的优先级。如果栈顶运算符的优先级 当前运算符的优先级则反复弹出栈顶运算符并输出直到栈空或栈顶为(或栈顶优先级小于当前运算符把当前运算符压入栈第 4 章 串、数组和广义表知识点表头和表尾表头整个广义表的第一个元素(可以是原子 也可以是子表 )一般不带这个括号 除非第一个元素本身就是一个子表表尾除去表头 剩下所有元素重新组成一个新广义表表尾一定是一个带括号的表 如果没有元素就是空表()空串是0个字符的串对于一个长度为n的字符串非空子串总数 n×(n1)/2​子串总数含空串 n×(n1)/2​1真子串含空串子串总数 - 1去掉本身 n×(n1)/2​串的特殊性特殊的线性表 每个数据元素都是字符模式匹配BF算法效率低 原因指针的回溯KMP算法效率高主串中搜索模式串返回首次匹配的起始位置求字串给定起始位置与长度截取一段连续字符串和字符的对比题型BF 模式匹配算法核心思想主串 S 和模式串 T 从某个位置开始一个一个比匹配就一起后移一旦不匹配主串回到“下一起点”模式串从头再来顺序串 SString 存储方式S[0] 存主串长度S[1] 开始才是真正字符S[1] 开始才是字符T[1] 开始才是字符匹配失败的如何回溯i代表主串从哪个字符开始匹配 j代表模式串的匹配到那个了假设当前已经匹配了j - 1个字符现在第j个字符不匹配计算匹配的起点i−j1下一轮匹配的起点i-j2KMP 模式匹配算法规定next[1]0 next[2]1计算next[j]求next[j]只看T[1] 到 T[j-1]这一段找它的“最长相等前后缀长度”next[j]最长相等前后缀长度1广义表的计算基础知识表头 (head)取出第一个元素表尾tail除了第一个元素以外的元素去除第一个元素长度 有几个元素深度 层数单独数左括号或者右括号的数目空子表的长度设为1 而不是0广义表表头、表尾嵌套运算从最内层括号开始由内向外计算(tail(head(L))) → 先算(head(L))把它当成新广义表再求 tail每次运算严格按照遵守规则tail 一定是带括号的表 删除第一个元素后 剩余的扩一层括号head 只拿第一个元素如果第一元素是子表就是带括号 如果是元素就直接取元素不带括号例题LS (e₁, e₂)((a), a)求表尾tail(LS) 删掉第一个元素后剩下所有元素组合成一个全新的广义表本题是atail(LS)自身是一张广义表广义表语法要求整体必须包一对外层括号 故再加一层(L(x,y,z))删表头 x剩余内容是两个独立元素(y、z)直接把两个元素放进一对外层括号就是完整的 tail((y,z))这里不用嵌套因为括号里直接放了两个独立元素不需要先打包一层而本题剩余只有单个元素 a必须先打包一层再套外层表括号因此出现两层Pasted image 20260629160618.png二维数组地址计算判断行优先/列优先前置条件设数组A[m][n]m 行 n 列每一行的元素是n 每一列的元素是m下标 i 行 j 列 下标从 0 开始Loc(0,0)首元素地址每个元素占k个存储单元行优先先存完完整一行再存下一行偏移元素个数i * n j地址公式 Loc(i,j)Loc(0,0)(i×nj)×k列优先先存完一完整一列再存下一列偏移元素个数j * m i//一定要确定这个m是乘的是j即列数地址公式 Loc(i,j)Loc(0,0)(j×mi)×k解题步骤先判断存储方式行优先还是列优先通过两组已知坐标 来得出这个m n计算所求地址距首元素的偏移元素个数代入地址公式易错点首元素不是Loc(0,0)而是Loc(1,1)第 5 章 树和二叉树知识点在任何二叉树中结点总数 N 叶子结点数 n0​ 度为1的结点数 n1​ 度为2的结点数 n2哈夫曼树是严格的满二叉树 树中不存在度为1节点 即n10同时叶子结点数 度为2的结点数 1Nn0​n2​n(n−1)2n−1完全二叉树数组存储规律节点下标为i通常从 1 开始计数左孩子下标2i右孩子下标2i 1前提条件孩子的下标必须≤ 总节点数 n否则该孩子不存在对于有n个元素的有序表二分查找最多比较的次数向下取整⌊log₂ n⌋ 1 最后加1二叉线索树的目的加快查找节点前驱和后继的速度题型叶子结点计算题基础知识补充总结点等式 n n_0 n_1 n_2 n_3 \dots(总节点等于各节点数之和)树的总边数 所有节点数度数之和树的总边数总结点数-1除根节点每一个节点上面都有一条边 步骤 列公式 n n_0 n_1 n_2 n_3 \dots 和边数度数n-1二叉树遍历核心规则前序根 → 左子树 → 右子树中序左子树 → 根 → 右子树后序左子树 → 右子树 → 根考点给二叉树求前中后序前序 每一个节点的左面画一个圈 然后从根节点出发用一根线连接到一起起点和终点都是根节点 先连到的先写中序每一个节点的下面画一个圈 然后从根节点出发用一根线连接到一起起点和终点都是根节点 先连到的先写后序每一个节点的右侧画一个圈 然后从根节点出发用一根线连接到一起起点和终点都是根节点 先连到的先写、给已知先序中序求后序/后序中序求先序递归法 只有中序遍历能区分一个节点的左、右子树归属因此必须搭配中序才能唯一还原整棵树进而求出第三种遍历序列教程Pasted image 20260628124221.png步骤画坐标系Pasted image 20260628124352.png然后找到根节点 根节点左面是左子树 右面是右子树依次类推根节点的子节点的左子树就是根节点子节点的左面 根节点的子节点的右子树就是根节点子节点的右面1.找最高点M2.在最高点M左边的区域内找最高点L3.在最高点M右边的区域内找最高点R4.连接L-M-R5.用L取代M递归下去 用R取代M递归下去最后进行连线求得二叉树二叉树广义表转遍历序列广义表标准格式根(左子树,右子树)e(,f(g))→ e 左空e 右 ff(g)→ f 左 gf 右空逗号一侧为空代表对应孩子不存在哈夫曼树哈夫曼树题型教程哈夫曼树构造把所有叶子权值升序排序循环选出当前最小 2 个权值合并生成新父节点父节点权值 两子节点权之和将新节点放回序列一定重复操作直到序列只剩 1 个根节点无强制左小右大左右交换不影响 WPL树形态不唯一但 WPL 固定尽量按规定左小右大带权路径长度 WPL 计算方法一路径长度根到叶子经过的边的数量根 0 层层数 路径长度路径长度只看叶子中间合并节点不参与加权求和 WPL\sum(叶子权值w_i × 该叶子路径长度l_i)方法二所有合并生成的中间节点全部相加 WPL哈夫曼编码分支标记规则统一规定左分支写 0右分支写 1左右互换则 0、1 全部颠倒不影响码长与 WPL。左小右大 左 0 右 1从根往下走到叶子走左分支拼接0走右分支拼接1一直走到叶子节点 最终得到就是哈夫曼编码二叉树和森林的相互转换森林转换二叉树数变二叉根相连兄弟相连留长子二叉树转换森林求掉根点右孩线 孤立二叉再还原右下兄弟连双亲第 6 章 图知识点深度优先遍历DFS: 栈广度优先遍历BFS: 队列四种基础图有向图有向、无权有向网有向、带权题目少见无向图无向、无权无向网无向、带权高频考题邻接矩阵本质上是一个顶点数 × 顶点数的二维数组方阵 占用空间 O(n²)只与顶点数n有关与边数无关邻接表的存储空间 顶点表边链表。顶点表n个顶点空间与顶点数有关。边链表如果是无向图每条边存 2 次有向图存 1 次。空间与边数有关。图的存储结构选择邻接矩阵空间开销固定开辟 n\times n 二维数组**空间复杂度 O(n^2)特点无论图有多少条边都要存满整张矩阵无边位置填 0/∞大量空间浪费适用场景稠密图边数 e 接近 (n^2)顶点之间几乎全连通邻接表空间开销顶点数组 每条边单独链表结点**空间复杂度 O(ne)特点只存储真实存在的边无边完全不占用空间适用场景稀疏图边数 e 远小于 n^2大部分顶点之间没有边题型通过有向图来求顶点的出度和入度邻接表邻接矩阵出度和入度入度是被指向 出度是指向顶点名1234入度出度邻接矩阵一行所有数字相加 该行对应顶点出度一列所有数字相加 该列对应顶点入度示例Pasted image 20260628190504.png邻接表结构组成顶点数组表头结点每个顶点单独一个表头边链表每个表头后接一条单链表存放所有从该顶点出发能到达的邻接点。示例Pasted image 20260628190837.png解题步骤给每个顶点建立表头对每个顶点 u遍历所有以 u 为起点的边u,v将终点 v 按顺序插入 u 的边链表中特点只存出边快速遍历一个点能直接走到哪些点统计出度只需要统计链表长度逆邻接表作用专门存所有入边快速求入度、找指向自己的顶点结构组成同样顶点表头数组每个表头后的链表存放所有指向该顶点的起点解题步骤每个顶点建表头遍历每条边u,v这条边是 v 的入边把起点 u 插入 v 的逆邻接链表特点: 链表长度 当前顶点的入度需要快速查询哪些点能走到当前点时使用无向网/无向图邻接矩阵邻接表邻接矩阵无向图、A[i][j] \begin{cases} 1 i、j 之间有边\\ 0 i、j 之间无边 \end{cases}只有 0、1 两种数字矩阵对称一行里 1 的个数 该顶点的度。示例顶点 0、1 相连\begin{bmatrix} 0 1 \\ 1 0 \end{bmatrix}无向网A[i][j] \begin{cases} w i、j 之间有边w为边上权值\\ 0 ij自身\\ \infty i、j 之间无边 \end{cases}数字0、权值w、无穷大(∞)没有 1矩阵依然对称一行里非 0、非(∞)元素的个数 顶点的度。示例顶点 0、1 相连权值 5\begin{bmatrix} 0 5 \\ 5 \infty \end{bmatrix}邻接表无向图无权边没有数值链表结点只存邻接点编号无向网带权边上有权值数字链表结点必须存【邻接点 权值】两个数据Pasted image 20260628192910.png最小生成树-Prim (普里姆) 算法和 Kruskal (克鲁斯卡尔) 算法原则权值最小不能有环路Prim (普里姆) 算法(不断的找下一个点)稠密图任意一点出发找最近且权重最小的边最后连接 并且进行重复操作Kruskal (克鲁斯卡尔) 算法不断的找下一条边稀疏图将所有边按权值进行升序排序然后进行从权值从小到大连接前提是不能出现环路从某个源点到其余各顶点的最短路径Dijkstra(迪杰斯特拉)算法每一次都选距离最近的点 然后更新Pasted image 20260628201850.png深度优先遍历DFS广度优先遍历BFS有向图/无向图有向图一条边存一次- 只有(v1,2)、(v1,3)无反向边- DFSv1,22 无出边回溯→v1,3- 如果只有(v1,2)没有(2,1)从 2 出发永远到不了 v1无向图一条边存两次- v1 邻接点 [2,3]- DFS 两种合法序列v1,2,3 /v1,3,2按邻接表顺序双向互通分支都能走到。类型核心特点无向 DFS双向通路一条路走到最深回溯后走同级分支无向 BFS双向通路一层一层遍历所有相邻顶点有向 DFS仅沿出边单向走无反向边则无法原路返回有向 BFS仅沿出边单向扩散分层遍历无法反向通行深度优先遍历特点不撞南墙不回头 一条路走到黑走到尽头再回溯序列不唯一实现工具递归 / 栈实现应用有向图一条边存一次/无向图一条边存两次邻接表的深度优先遍历广度优先遍历特点一层一层向外扩散先访问所有直接邻居再访问邻居的邻居队列实现实现工具队列实现应用有向图一条边存一次/无向图一条边存两次邻接表的广度优先遍历AOE网的关键路径问题基础概念AOE网顶点表示事件边表示活动边上的权值表示活动持续时间起始活动只有箭头出 (入度为 0 的点)结束活动只有箭头进 出度为 0 的点考点AOE 网求最早完成时间原则从起点往终点算每到一个点取“前面所有路径时间的最大值”一个事件要发生必须等它前面的所有活动都完成 所以计算最大值步骤从起点开始往后算遇到一个点有多个前驱就取最大值最后终点的 ve 值就是工程最早完成时间求每个活动的最早开始时间和最迟开始时间活动最早开始时间起点事件的ve活动最迟开始时间终点事件的vl−活动持续时间​确定哪些活动是关键活动画出关键路径最早开始时间 最迟开始时间的活动就是关键活动。得出关键活动 把关键活动连起来就是关键路径第 7 章 查找知识点题型哈希表散列表构造哈希表的方法画表通过哈希表的地址范围来画表计算哈希值H(\text{key}) \text{key} \% p填表处理哈希表冲突方法线性探测法核心思想如果计算出的哈希地址 d 已经被占用了就依次检查 d1, d2, d3 \dots 直到找到一个空闲的位置。如果走到了哈希表的末尾就折返回表头0号位置继续往下找。数学公式d_i (H(\text{key}) i) \% m \quad (i 1, 2, 3 \dots)H(\text{key})初始哈希地址i冲突发生的次数第几次探测m哈希表的表长地址总数二次探测法平方探测法核心思想以冲突点为中心左右跳跃着寻找空位先向右跳 1^2 步再向左跳 1^2 步再向右跳 2^2 步……数学公式d_i (H(\text{key}) \pm i^2) \% m \quad (i 1, 2, 3 \dots)d_1 (H(\text{key}) 1^2) \% m 往右跳 1 步d_2 (H(\text{key}) - 1^2) \% m 往左跳 1 步d_3 (H(\text{key}) 2^2) \% m 往右跳 4 步d_4 (H(\text{key}) - 2^2) \% m 往左跳 4 步\dots 依次类推。计算 ASL平均查找长度查找成功计算公式- \text{ASL}_{\text{succ}} \frac{\text{表中所有元素查找成功的比较次数之和}}{\text{表中元素的总个数 } n}表中的元素总个数 n指的就是你实际存进哈希表里的关键字数字的总数量查找失败的计算公式线性探测法从当前的初始地址 i 开始用肉眼往右数格子一直数到“第一个空格子”为止。一共数了几个格子包括空格子自身C_i 就是几。如果数到表尾还没遇到空格就折返回 0 号位置继续数。公式\text{ASL}_{\text{unsucc}} \frac{\sum_{i0}^{p-1} C_i}{p}二次探测法方法对于任意一个初始地址 i它的探测路径严格遵循以下顺序第 1 次比较直接看地址 i第 2 次比较看地址 (i 1^2) \% m第 3 次比较看地址 (i - 1^2) \% m 负数记得加表长 m第 4 次比较看地址 (i 2^2) \% m第 5 次比较看地址 (i - 2^2) \% m……以此类推。公式\text{ASL}_{\text{unsucc}} \frac{\sum_{i0}^{p-1} C_i}{p}判停铁律在这条路径上只要某一步算出来的地址在表里是“空的”数数立刻停止这一步是第几次该位置的 C_i 就是几。第 8 章 排序知识点题型大根堆/小根堆概念堆是一颗完全二叉树除了最后一层外其他层的节点数都是满的 最后一层的节点必须从左到右连续排列中间不能有空缺。大根堆父结点 ≥ 左右孩子。小根堆父结点 ≤ 左右孩子。步骤画二叉树层序序列然后分析判断大根堆/小根堆直接插入排序插入规则每次将一个新元素插入到前面的已排序序列中时从已排序序列的末尾即最大值开始从右往左依次比较折半插入排序前提条件所插入的序列为有序数列插入步骤初始化 (low0,\ highi-1)循环条件(low \le high) 一旦条件不满足 就停止二分中点公式(mid\lfloor \dfrac{lowhigh}{2} \rfloor) 整数除法向下取整目标数字比中间值小插入点一定在左半边 左边界收缩highmid−1目标数字比中间值大插入点一定在右半边 右边界收缩lowmid1希尔排序分组进行排序根据不同增量d来排序按增量 d 分组下标差值为 d 的元素为一组每组内部执行直接插入排序将第 i 个元素插入到前面已经排好序的子序列中从后往前一个个比对逐步缩小增量直到 (d1)整体一次直接插入保证完全有序快速排序处理原则第一趟先处理整个表↓把枢轴放到最终位置↓分成左子表 和 右子表↓先处理左子表↓左子表处理完↓再处理右子表一趟只确定一个枢轴的位置 然后再分别处理它左边和右边圈出基准圈出当前序列的第一个数左右归类扫视剩下的数字把比 第一个数小的挑出来放左边比 第一个数大的挑出来放右边处理左子序列圈出基准左右归类递归求左右序列等左子序列 处理右子序列圈出基准左右归类递归求解左右序列再次递归排序左右子序列简单选择排序从头到尾扫描序列 找出最小的关键词与第一位进行交换把剩下的无序队列中选出最小的关键词与剩下的无序队列的最后一位进行交换堆排序对于给出的这个序列按照顺序进行构造这个完全二叉树这个序列可以看作层序遍历第一个非叶子节点n/2-1(非整数进行向下取整)解题步骤堆构造的完全二叉树进行编号层序编号 起始编号是0然后通过计算n/2-1 找到第一个非叶子节点最后比较这个节点和其最大的孩子节点的大小如果小于就进行交换 同时也要进行最大的孩子节点的最大的孩子节点的比较大小比较完成后 n/2-1 减去1 然后再次进行比较 知道减到0归并排序步骤初始状态数组中每个独立元素单独成为一个有序小组。逐轮两两合并从左向右相邻两个有序小组取出双指针比较元素合并为一个更长的有序组若本轮分组总数为奇数最末尾剩余单独一组无配对直接保留本轮不参与合并顺延到下一轮处理仅最后一轮只剩两组时强制合并得到完整有序数组。重复循环每轮合并完成后小组长度翻倍持续两两归并直到整个数组合并为单一有序组排序结束。