数据结构笔记

1、数据结构笔记基础：数据结构与算法(一) 数据结构基本概念数据( data )：是对客观事物的符号表示， 在计算机科学中是指所有能输入到计算机中并被 计算机程序处理的符号总称 数据元素( data element )：是数据的基本单位，在计算机中通常被当做一个整体进行考虑 和处理 数据对象( data object )：性质相同的数据元素的集合，是数据的一个子集 数据结构( data structure )：相互之间存在一种或多种特定关系的数据元素的集合 4 类基本结构：集合、线性结构、树形结构、图形(网状)结构数据结构的形式定义为数据结构是一个二元组Data Structure =(D,S)，

2、其中D是数据元素的有限集，S是D上关系的有限集数据结构定义中的 “关系” 描述的是数据元素之间的逻辑关系， 因此又称为数据的逻辑结构 数据结构在计算机中的表示(映像)称为物理结构(存储结构) 计算机中表示信息的最小单位是二进制中的一位， 叫做 位( bit )，一到若干位组成一个位 串表示一个数据元素，这个位串称为元素或结点 数据结构之间关系在计算机中的表示有两种： 顺序映像、 非顺序映像， 并由此得到两种存储 结构： 顺序存储、链式存储，前者运用相对位置表示数据元素间的逻辑结构，后者借助指针 任何一个算法的设计取决于数据(逻辑)结构，而实现依赖于存储结构 数据类型是一个值的集合和定义在这个值

3、集上的一组操作的总称 数据类型分两种：原子类型、结构类型，前者不可分解(例如 int 、char 、float 、void )， 后者结构类型由若干成分按某种结构组成， 可分解， 成分既可以是非结构的也可以是结构的(例：数组)抽象数据类型( Abstract Data Type )：是指一个数学模型及定义在该模型上的一组操作( P8)抽象数据类型格式如下：ADT抽象数据类型名数据对象： <数据对象的定义 > 数据关系： <数据关系的定义 > 数据操作： <数据操作的定义 > ADT抽象数据类型名基本操作格式如下：基本操作名(参数表)初始条件： <初始条

4、件描述 > 操作结果： <操作结果描述 >多形数据类型( polymorphic data type )：是指其值得成分不确定的数据类型(P9)抽象数据类型可由固有数据类型来表示和实现(二) 算法(概念)和算法分析(时、空性能)算法(algorithm ):对特定问题求解步骤的一种描述算法5特性：有穷、确定、可行、输入、输出1有穷性：算法必须在可接受的时间内执行有穷步后结束2、确定性：每条指令必须要有确切含义，无二义性，并且只有唯一执行路径，即对相同的 输入只能得相同输出3、可行性：算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入：一个算法有一到多个输入，并取自某

5、个特定对象合集5、输出：一个算法有一到多个输出，这些输出与输入有着某些特定关系的量 算法设计要求(好算法)：正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能够判断出这个输入不符合规范要求，并能有合理的处理方式。算法效率的度量：(1)事后统计：程序运行结束后借助计算机内部计时功能，缺点一是必须先运行依据算法编制的程序，二是受限于计算机软硬件，导致掩盖了算法本身的优劣(2 )事前分析估计：消耗时间影响因素：算法策略、问题规模、编程语言、编译程序产生的机器码质量、机器执行指令的速度撇开各种影响因素只考虑问题的规模(通常用整数量n表示)，记为问题规模的函数算法时间取决于控制结

6、构(顺序，分支，循环)和固有数据类型操作的综合效果书写格式：T (n) = O( f (n) f(n)为n的某个函数时间复杂度：算法的渐近时间复杂度(asymptotic timecomplexity )，它表示随冋题规模的增大，算法执行时间的增长率和f (n)的增长率相冋以循环最深层原操作为度量基准频度：该语句重复执行的次数算法的存储空间需求：空间复杂度(space complexity ):算法所需存储空间度量，记作S (n) = 0(f (n),其中n为问题规模的大小排序专法时间复亲度空冏复聽 度复杂性平均汁况R*.坏衬-；比贞按捕入搏 序o(n2>o（ir）0(100(1)帝尔誹

7、序0(1)较？.杂O(n">0(11*)0(100(1)O(u5< ?(EtfOg2U)不雄宅较览杂0(1內0(1)简单堆排序0( ill ogn)O(hl0$2ll)0(1)不穂支较更杂归扌非序Oflllo £211)0(1110 C211)O(n)虽就44序卄卄)b勺口 csc：ri.co较更杂rn/wh usl9i-、线性表（一）线性表基本概念线性表（linear list） : n个数据兀素的有限序列结构特点：存在唯一的被称作“第一个”、“最后个”的数据兀素，且除了第一个以外每个兀素都有唯一前驱，除最后一个以外都有唯一后继在复杂线性表中存在：数据项 -&

8、gt; 记录-> 文件，例如每个学生情况为一个记录，它由学号、性别. 数据项组成，多个学生记录组成一个文件在形如（al, . , ai-1 , ai , ai+1 , . , an）中，ai-1 领先于 ai , ai 领先于 ai+1，且形 成直接前驱元素，直接后继元素关系元素个数n定义为线性表长度，n=0为空表相关操作算法见书（P20）（二）线性表顺序存储结构和链式存储结构（1 ）线性表顺序表示和实现线性表顺序存储在一组连续的存储单元中，链式存储则不要求；顺序结构可以随机访问，链式结构可以无限扩容确定存储位置（计算公式）：第i个元素：LOC（ai）= LOC（a1）+（i-1）*L

9、L 是偏移量，即每个元素占用存储单元第ai+1个元素：LOC（ai+1）= LOC（ai） +L al（起始地址或基地址）C语言下标从"0”开始，则表中第i个元素是L.elem i-1当对线性表进行操作时，被操作元素后面的元素角标会相应变化（前移、后移），算法（P24）（2 ）线性表链式表示和实现特点：用一组任意的存储单元存储线性表的数据元素（存储单元不一定连续）结点存储数据元素及直接后继的存储位置信息，两个域：数据域和指针域，指针域中存储的信息称为指针或链，仅含有一个指针域故又称线性链表或单链表链表的插入：先增加一条指针再修改原指针头指针指向第一个数据兀素的存储位置，最后一个结点的

10、指针为空（NULL链表表示方法及算法（P28）单链表第一个结点前加一个头结点Head,其数据域可为空也可存储一些附加信息（链长等）假设p是指向线性表中i个元素（ai ）的指针，则p->next是指向i+1个数据元素 在单链表中，取得第i个元素必须从头指针开始寻找，因此单链表是非随机的存储结构 线性表指逻辑结构，从抽象数据层面来说顺序表和链表指物理存储结构逻辑结构：离散、线性、层次、网状应用见书算法二、栈和队列（一）栈的基本概念栈（stack ）是限定仅在表尾进行插入或删除操作的线性表表尾为栈顶，表头为栈底，遵循后进先出原理（last in first on, LIFO），不含元素则为空栈

11、操作：在栈顶插入（入栈）和删除（出栈），栈初始化、判空、取栈顶元素（算法P45）（二）栈的顺序存储和链式存储顺序栈，即栈的顺序存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元 素，同时附设指针top指示栈顶元素在顺序栈中的位置初始栈时不应限定栈的最大容量，基本做法是先为栈分配一个基本容量，然后在应用过程中，不够用再逐段扩大（算法P46）（三）递归栈与递归的实现：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数阶乘函数、2阶Fibonacci数列、Ackerman函数、3阶Hanoi问题（多阶呢？）（ P54）函数调用函数执行过程笔记（P56）（四）队列队列先

12、进先出（first in first out，FIFO），队尾一端插入，队首一端删除元素（日常 排队）队列与栈均有八种基本操作（P59）,队列一般用链表实现，栈用顺序表实现双端队列（限定操作的队列）（P60)（五）栈和队列的应用链队列、循环队列（P60）,离散事件模拟（银行接待工作（P65）（六）特殊矩阵的压缩存储如何存储矩阵的元，使矩阵的运算有效进行。高级语言常用二维数组存储阵元 面对如高阶矩阵，多值相同矩阵和多零元素矩阵进行压缩存储节省空间 压缩存储：为多个值相同的元只分配一个空间，对零元不分配值相同元素或零元素具有分布规律则称为特殊矩阵，反之为稀疏矩阵具体应用与算法（P95）三、树与二叉

13、树（一）树的基本概念树是非线性数据结构，以分支关系定义的层次结构树是n （ n>=0）个结点的有限集详见（P118）,基本术语（P120）（二）二叉树1. 二叉树的定义及其主要特征：二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树” （left subtree ）和“右子树”（(right subtree )。性质：1.2.3. J满二叉树：完全二叉树:4.5.2.二叉树的顺序存储结构和链式存储结构顺序存储，用一组地址连续的存储单兀依次自上而下、自左至右存储完全二叉树上的结点兀素，即将完全二叉树上编号为i的结点依次存储在如上定义的一位数组下标为i-1的分量中。1 23456

14、789链式存储，每个结点中至少包含三个域,左指针，数据，右指针，称作“二叉链表”增加一个双亲指针域，则称作“三叉链表”详见P126-1273.二叉树的遍历遍历二叉树，每个结点均被访问一次，且仅有一次。在限定先左后右的访问序列后，有三种遍历方式：先序（DLR，中序（LDR ,后续（LRD）P129算法6.1 （波兰式层次遍历，无论那种遍历方式，对含n个结点的二叉树，时间复杂度都为0（n ）,空间摘要：对于n个结点的二叉树，在二叉链存储结构中有n+1 (2n- (n-1 )个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索概念：加上了线索的二叉链表称为线

15、索链表，相应的二叉树称为线索二叉树(ThreadedBin aryTree)。构造方法：(三) 树与森林1. 树的存储结构链表结构：1.双亲表示法 2.孩子表示法 3.孩子兄弟表示法详见P1352. 森林与二叉树转换 左孩子右兄弟3. 树与森林的遍历先序、中序遍历，详见P139当以二叉链表做树的存储结构时，树的先序=二叉树先序、树的后序=二叉树中序(四) 树与二叉树的应用1. 二叉排序树二叉排序树(Bi nary Sort Tree )，又称二叉查找树(Bin ary Search Tree )，亦称二叉 搜索树。定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：(1) 若左子树不空

16、，则左子树上所有结点的值均小于它的根结点的值；(2) 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3 )左、右子树也分别为二叉排序树；(4 )没有键值相等的节点。此图是B5T3.8/91图二1068BST,但只有图一是 AVL tree图一，图二都是哈夫曼（Huffman ）树和哈夫曼编码6/At_ 一(4 )(72> (T)此图是B5T查找：步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，递归查左子树。 若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。2. 平衡二叉树（AVL）定义：它或者是一颗空树， 或者具有以下性质的二叉

17、树：它的左子树和右子树的深度之差（平衡因子）的绝对值不超过 1且它的左子树和右子树都是一颗平衡二叉树。平衡因子（bf）:结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1哈夫曼树是一类带权路径长度最短的树，又称最优树。路径和路径长度概念：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一结点的路径长度之和。推广到一般情况，考虑带权结点：结点的带权路径长度为从该结点到树根之间的路径长度与结点上的权值的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和，记作WPL=带权路径长度WPL最小的二叉树称为

18、最优二叉树或哈夫曼树利用二叉树来设计前缀编码哈夫曼算法构造哈夫曼树（P145）约定左分支表示字符“ 0” 右分支表示字符“ 1 ” 则从根结点到叶子结点 的路径上分支字符组成 的字符串作为该叶子结 点字符的编码。一般情况，当带有权值时，本质上就是设计一棵哈夫曼树，得到二进制前缀编码=哈夫曼编码算法详见P147四、图（一）图的基本概念图是一种数据结构，加上一组基本操作，构成的一种抽象数据类型详见（P156）途中数据元素通常称为顶点，V是顶点的有穷非空集合；VR是两个顶点的关系集合， 若v,w属于VR则v,w表示从v到w的弧，称v为弧尾（初始点），w尾弧头（终结点）此时图是有向图，若 v，w属于V

19、R必有w, v属于VR则以无序对v，w，表示v和w的 一条边，此时称图为无向图完全图有向完全图边或弧很少（enlogn ）的图，称为稀疏图，反之为稠密图 边或弧所具有的相关数称为权，带权的图称为网子图连通图（二）图的存储及基本操作1. 邻接矩阵法用两个数组分别存储数据元素（顶点）的信息，和数据元素之间的关系（边或弧）的信息 算法详见（P161）2. 邻接表法邻接表是图的一种链式存储结构。算法详见（P163）（三）图的遍历1. 深度优先搜索（DFS图示及算法（P168）详见（P169）类似于树的先根遍历，可把图转化为树操作。2. 广度优先搜索类似于树的层次遍历，可把图转为树操作。（四）图的基本应

20、用1. 最小（代价）生成树（P173）普里姆算法构造最小生成树：克鲁斯卡尔算法构造最小生成树:2. 最短路径（P186）在图中从顶点 A到B,找一条所含边（弧）最少的路径，从A开始做广度优先搜索，直到B结束，则称为最短路径。可推广的含权值的情形，此时最短路径度量是路径上权值之和带权有向图：源点-> 终点迪杰斯特拉算法：3. 拓扑排序由某个集合上的偏序得到该集合的全序偏序：若集合X上的关系R是自反的、反对称的和传递的， 则称R是集合X上的偏序关 系；设R是集合上的偏序，如果对每个x, y属于X必有xRy或yRx,则称R是集合X上的全序关系。详见（P180）4. 关键路径（最长路径）（P18

21、3）五、查找（一）查找的基本概念在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元 素的过程叫做查找。 也就是根据给定的某个值， 在查找表中确定一个关键字等于给定值的 记录或数据元素。（二）顺序查找法1顺序查找：核心：从数据的第一个元素开始，依次比较，直到找到目标数据或查找失败。1. 从表中的第一个元素开始，依次与关键字比较。2. 若某个元素匹配关键字，则查找成功。3. 若查找到最后一个元素还未匹配关键字，则查找失败。2. 时间复杂度：顺序查找平均关键字匹配次数为表长的一半，其时间复杂度为0(n)。3顺序查找的评估：顺序查找的优点是对表无要求，插入数据可在0(1)内

22、完成。缺点是时间复杂度较大，数据规模较大时，效率较低。(三) 折半查找法算法要求：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 查找过程：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比 较，如果两者相等，则查找成功否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录， 使查找成功，或直到子表不存在为止， 此时查找不成功。(四) 散列(Hash)表哈希表定义：是根据关键码值 (Key value)而直接进行访问的数据结构。也就是说，它

23、通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M存在函数f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该 关键字的记录在表中的地址，则称表M为哈希(Hash )表，函数f(key)为哈希(Hash)函数。基本概念：若关键字为k,则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记 录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。对不同的关键字可能得到同一散列地址，即k1承2，而f(k1)=f(k2)，这种现象称为冲突(英语：Collisio n )。具有相同函数值的关键字对

24、该散列函数来说称做同义词。综 上所述，根据散列函数 f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的 地址集(区间)上，并以关键字在地址集中的像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function )，这就是使关键字经过散列函数得到一个随机的地址”从而减少冲突。(五) 字符串模式匹配子串的定位操作是要在主串S中找出一个与子串T相同的子串，通常把主串S称为目标，把子串T称为

25、模式，把从目标S中查找模式为T的子串的过程称为 模式匹配”1. Brute-Force算法的设计思想Brute-Force 是普通的模式匹配算法。将主串S的第1个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较，直到主串的一个连续子串字符序列与模式相等，返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功；否则，匹配失败，返回值0。2. Brute-Force 算法的特点：每次遇到匹配不成功的情况，指针i都要移到本次匹配的开始位置的下一位，称这样的指针移动为回溯。指针的回溯越多，简单模式匹配的执行次数越多Brute-Forc

26、e 匹配算法的最坏时间复杂度为0(n*m), 般情况下BF算法的时间复杂度为0(n+m)3. KMP算法的改进每当一趟匹配过程中出现字符比较不等时，不需回溯指针i，而是利用已经得到的部分匹配”的结果将模式向右滑动”尽可能远的一段距离后，继续比较KMP算法的时间复杂度可以达到0(m+n)4. KMP 算法的设计思想假设以指针i和j分别指示主串和模式中正待比较的字符，令i的初值为0, j的初值为0若在匹配过程中，Si=Pj，则i和j分别增1否则i不变，而j退到nextj的位置再 比较，若相等，则指针各自增1否则j再退到下一个next值的位置，依次类推若令nextj=k ，则nextj表明当模式中第

27、j个字符与主串中相应字符失配时，在模式中 需重新和主串中该字符进行比较的字符的位置模式串的next函数定义为f 0j=1nextjl='* "日* k I Xk<j H,P1P2,.P(+j.k+2-Pj*if UJ_|当此集合不空时I 1英他情况例如：j12345678模式串abaabcacnextj01122312第一逍主串模式* i= 2a c a 11孔曰b shr日右a bt ； = 2 nejctZl = 1主串* i=2第二趟acabaabaabcacaabc模式af ; = 1 rtejtzElJ O主串I i = 3 4 »=8第三趟acab

28、aabaabcacaabc模式a b a a b cf j = l一f j = 6= 3第四轴主串模式| *呂 |= 14cabaabaAbcacaabc(a b)a # b c a c f > = 3* t ； = S利用模式的next函数进行匹配的过程示例（六）查找算法的分析及应用六、排序（一）排序的基本概念将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。分内部排序和外部排序， 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成， 则称此类排序问题为外部排序。内部排序的过程是一个逐

29、步扩大记录的有序序列长度的过 程。（二）插入排序直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。有序I待排序I对待排序的序列逐亍SS入，完为止I怖有元養全部播入.排吊完施（三）气泡排序冒泡排序的基本思想是，对相邻的兀素进行两两比较，顺序相反则进行交换，这样，每一趟会将取小或取大的兀素浮"到顶端，最终达到完全有序相邻元素两两比SE.反序则交換第一影完毕.将最大元累9浮到数组顶端同理,SI二轮将第二大元素B俘到数坦顶端排序完成（四）简单选择排序简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据兀素中选择最小（或最大

30、）的一个兀素作为首兀素，直到所有兀素排元为止，间单选择排序是不稳疋排序。在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前 最小，交换是个比较耗时的操作。 其实我们很容易发现， 在还未完全确定当前最小元素之 前，这些交换都是无意义的。我们可以通过设置一个变量min，每一次比较仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。代码实现很简单，一起来看下。（五）希尔排序希尔排序是基于插入排序的，首先回顾一下插入排序，假设插入是从左向右执行的，待插入兀素的左边是有序的， 且假如待插入兀素比左边的都小，就需要挪动左边的

31、所有兀素，如下图所示：圉t札图丄：產人石边的怕rriy王琵要o曰除l己立左边的七个圧子書问芒那抑1圏M所示,狷btai入时,酥排施足祥個眄:刃国走叵隔羽元春做擂入转序,然后环叵陽r車 哥研SA带亭r直乱闻關瞌小如”II 1 III. 1T九為inn*iniW-Filllll帕ftf1ojtsrlefrininnrir亘3和妙；octe L_E叩rni刨】社匮泪主子恃描人啡.学数1G星木的图形乖心遊更昏曷形藏堆把囲商锦1 r Mffism r轲元SE施等于1C» ；rr40匱5和蛋6 :石鬲分別为知和12执行完插入徘帛后丙效需相比简单插入排序，大间隔地做插入排序有两个好处:一、大间隔直

32、接导致需要挪动的数据稀少，且数据挪动的效率高，图5中一次挪动可以跨越40个位置；二、 经过前一步大间隔的插入排序后，整个数组从整体上粗略地看已经有了明显的顺序，后一步小间隔的插入排序时，一部分操作是不需要挪动数据的，再次减少了挪动数据的次数。间隔的序列：间隔的常用序列，通过递归表示：h=3*h+1。( 1,4,13,40,121)各种基于实验的评估，估计它希尔排序的效率：“没有理论上分析希尔排序的效率的结论,的时间级从0们人(3/2)到0们人(7/6) ” -1。(六) 快速排序快速排序算法的策略是这样的： 首先把数组用某个值分为两个子数组，且称这个值为分组值,一个子数组中的元素均小于分组值，

33、另一子数组则均大于等于分组值，这里的子组内并不排序；然后，再分别对两个子组进行再分组，重复递归这个过程，直到最后每两个元素作为一 组进行再分组，整个数组就排好序了。分组过程具体如下：同时从左往右和从右往左扫描数组，记扫描标记位为LP和RP。在LP 一边，若发现元素小于分组值则跳过（即向右移动一位检查下一个元素），否则等待RP的扫描；RP若发现元素大于等于分组值跳过，直到找到小于分组值的元素，然后LP和RP位置的元素交换，重复这个过程，直到 LP和RP相遇。如图7,8所示，以11号元素为分组值，LP停在0号位置，RP跳过10号，停在图7中 的9号位置（粉色柱），然后 0号和9号交换，后续重复这个

34、过程。nghlScanEntering qukckSortQ; will partition flO-11)Aleftpivotright 日 canWill scan圍7和屋8 :以11号柱作为分裁1.0号#匸夕号哇子将交涣要9： 100个元春兰数自泾过两丸井组话兰致果分组值的选择，可以想见，理想的分组值应该是待分组元素的中值，这样分组后子组在数量少几乎是一半对一半，不过找中值无疑增加了算法的工作量。图7中采用了更简单的方式，直接选数组最右边的元素为分组值，分组结束后，再把这个值交换到 LP和RP相遇的位置，假如初始数组是从大到小排序的，这种情况下，选择最右边的元素作为分组值，其区分 度就很

35、差了。更好用的方法是所谓的取首尾中三项数据的中值或者平均值。通过对算法过程的描述可知，其时间复杂度应该为：O(N*logN)，比简单排序和希尔排序都要快。(七) 堆排序堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：大顶堆小顶堆同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子nD5Q4540202535301015该数组从逻辑上讲就是一个堆结构，我们用简单的公式来