# 大话数据结构 ## 第一章 绪论 **数据项**是最小单位，组成**数据元素**。一般只讨论数据元素。 **数据结构**：相互之间存在一种或多种特定关系的数据元素的集合 1. 逻辑结构： * 集合。各个元素平等。 * 线性：一对一 * 树：一对多 * 图：多对多 2. 物理结构：逻辑结构的储存形式 * 顺序存储：如数组 * 链式存储：如链表，指向下一个元素的地址 **数据类型**：不同类型分配不同内存 * 原子类型：不可再分，整型、字符型等 * 结构类型：原子类型组合而成 ## 第二章 算法 算法：解决特定问题求解步骤的描述。指令的有限序列。 好的算法： * 正确：合法输入有正确输出，边界条件也能正确 * 可读 * 健壮：不合法输入也能做出处理 * 效率高：时间、空间 ### 计算成本： 计算对运行时间有消耗的基本操作执行次数 #### 时间复杂度 * 常数阶：O(1) 分支结构 * 线性阶：O(n) 循环n次，里面是O1操作 * 对数: O(logn) 每次循环，都离结束更近 * 平方阶：O(n2) 嵌套，On套On。包括外面i，里面从i开始，也是On2 ![image-20191008164158431](https://tva1.sinaimg.cn/large/006y8mN6gy1g7qvv4rnvwj31og0t8asq.jpg) #### 空间复杂度 * 原地：O(1) ## 第三章 线性表 ### 数组。 排队，有顺序。一对一。 存取时间O(1)。删除增加，O(n) ![image-20191008172628249](https://tva1.sinaimg.cn/large/006y8mN6gy1g7qx5dsgb0j31as0o8tsk.jpg) #### 链表 存取O(n)，插入O(1) 删除表：留两个变量p和q，p获取当前节点，q获取p指向的节点，然后释放p。q给p，以此往复 ![image-20191008174440768](https://tva1.sinaimg.cn/large/006y8mN6gy1g7qxoagsisj31jp0u07wh.jpg) ### 静态链表 给没有指针的语言，来描述单链表。用数组代替指针。 数组每个下标对应两个：数据data，next指针的cur 有删改的时候，直接放在后面，然后用cur指向新增的地方 ### 循环链表 用尾指针来表示循环链表 ![image-20191009171456862](https://tva1.sinaimg.cn/large/006y8mN6gy1g7s2fne2m8j31oe08uwj1.jpg) 这样查找尾节点只用O(1)，头节点是rear.next.next，也是O(1) ### 双向链表 多写一个指针记录上一个节点。 ## 第四章 栈与队列 ### 顺序存储结构 下标为0的一端作为栈底。 定义top变量存栈顶元素位置。空栈的top为-1。 需要事先确定数组的存储大小。 ### 两栈共享空间 很可以一个栈快满，另一个栈还空。 ![image-20191009180043414](https://tva1.sinaimg.cn/large/006y8mN6gy1g7s3r969gdj30nw0b4q5a.jpg) 只要top1和top2不见面，两个栈就能一直使用 适合一个栈增长，另一个栈减少的情况。 ### 栈的链式存储（链栈） ![image-20191009180353549](https://tva1.sinaimg.cn/large/006y8mN6gy1g7s3ujbtzlj30li0tmdkb.jpg) 除非内存满，不然栈不会满 进栈和出栈都是O(1) 如果元素大小变化不可预料，用链栈。不然用顺序栈 #### 栈的应用 * 实现递归 * 括号 遇到左括号就入栈，遇到右括号就出栈。期间算出其中内容。 * 乘除、加减 1. 逆波兰，通过规则变成后缀表达式。 * 遇到数字输出， * 如果是符号，且比栈顶符号优先级更高，就入栈。 如栈顶为+，输入\*，则入栈 * 如果是比栈顶优先级低，那么全部清空。 如栈顶\*，输入+，就清空栈输出，并把+入栈 * 如果是（，那么入栈，等待遇到），然后把其中包裹的内容都输出 2. 遇到数字进栈，遇到符号，把栈顶两个数字出栈，运算，再塞回去。 ### 队列 先进先出的排队。允许插入的叫队尾，允许删除的叫队头 #### 循环队列 出栈后不一定要全部移动，只需要移动头指针即可 这样的话为了不溢出，就需要也移动尾指针。 ![image-20191010105321278](https://github.com/joeyZhouYicheng/notes/tree/2876bad0216a7a05e7fcbe85cf58f8f45210350d/Library/Application%20Support/typora-user-images/image-20191010105321278.png) 当`rear == front`的时候，就会无法判断队列是否为空 * 设定一个标志位flag，来判断是否为空 * 必须保留一个位置，不能让`rear=front`的情况发生 #### 队列的链式存储结构 链表队列。比循环队列更灵活 ![image-20191010110323079](https://tva1.sinaimg.cn/large/006y8mN6gy1g7sxbbfkcpj31980e642u.jpg) ## 第五章 string 根据字符串的编码，来比较字符串的大小。如查字典的过程。 * 顺序存储 一般把字符串长度保存在0下标的位置，或结尾的位置。 一旦有对字符串有预定义的大小，那么每次对字符串进行操作，就有可能溢出 * 链式存储 一个节点存放一个或多个字符。没被占满的，用#补全 ![image-20191010112129659](https://tva1.sinaimg.cn/large/006y8mN6gy1g7sxu5sgqej31mk06477g.jpg) 总的来说不如顺序存储 ### 模式匹配算法 子串的定位操作，就叫模式匹配 * 双循环，一个个字符比对 太低效 （外循环可以到内循环长度就停下，这样可以少跑内循环的距离） * kmp 双循环对于一些已经匹配过的字符串，还会再匹配一遍，kmp都省略掉了。 1. 如果已知a与后面的b到e都不相同，且一开始a到e都是匹配的。 比如`abcdefgab`里面找`abcdex` 因此可以直接跳过外循环的b到e。换言之，外循环的i不变小。内循环跑到1 1. 如果后面有重复 如`abcabcabc`里找`abcabx` 那么内循环的j就跑到3，因为第二轮的时候，ab已经比较过了。 ![image-20191010171040989](https://tva1.sinaimg.cn/large/006y8mN6gy1g7t7xiwnb1j30xw0bun12.jpg) ## 第六章 树 根节点唯一，子节点互不相交。即子节点不能互连，只能从上到下。 * 度degree：节点有多少子节点。 叶节点度为0。整个树的度，就是节点中最大的度。 * 层次level 最大层称为深度或高度 * 有序/无序 如果从左至右不能互换，就是有序 * 森林 多棵互不相交的树的集合。 ### 存储结构 因为可以一对多，因此无法用物理存储位置反映逻辑关系。 * 双亲表示法 每个节点一定有双亲。因此每个节点要存一下双亲在哪。 如果有从根到叶的需要，可以再存一下第一个左节点的指针 如果有表示兄弟关系的需要，可以再存一下右兄弟的指针 * 孩子表示法 兄弟节点之间，是用顺序存储，用链表指向子节点。 因此每个节点都存有数据和指针两组数据。 ![image-20191011210638121](https://tva1.sinaimg.cn/large/006y8mN6gy1g7ukddcgfbj30so0kkgr7.jpg) 也可以再加一个指针，指向自己的双亲 * 孩子兄弟表示法 一个指针指子节点，一个指针指右边第一个兄弟节点 这就把一个复杂的树变成一颗二叉树 ![image-20191011210941529](https://tva1.sinaimg.cn/large/006y8mN6gy1g7ukghrasij30lw0mkjw1.jpg) ### 二叉树 左右子树有顺序，从小到大。 * 满二叉树：全部塞满 * 完全二叉树：横着标数字，不能有缺 ![image-20191011212137243](https://github.com/joeyZhouYicheng/notes/tree/2876bad0216a7a05e7fcbe85cf58f8f45210350d/Library/Application%20Support/typora-user-images/image-20191011212137243.png) #### 存储结构 * 数组 只有是完全二叉树，才可以放在数组当中。 其他的不行。不然右斜树就太浪费空间了。 * 链表 二叉链表，数据+左指针+右指针 #### 遍历 * 前序：从上到下，先左，深度优先 * 中序：从下到上，左到右。【相当于竖着从左到右的遍历】 ![image-20191014171239709](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xuguuis4j30rs0ngdnh.jpg) * 后序：先按掉根不管，一根根分支遍历。先下后上，先左后右，最后到根。 ![image-20191014171352267](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xui27tr7j30nq0qagtd.jpg) * 层序：左到右，广度优先 #### 线索二叉树 二叉树有很多空指针，尤其叶子比较多的时候。 用空指针记录前驱和后继的节点。【或者说是二叉树上左边和右边的节点】 指向的指针叫线索。 相当于变成一个双向链表。 ![image-20191014172340058](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xus85q5pj31ik0hsgth.jpg) 不过这需要增加一个标志位，来表明是指上面还是下面。 【为啥感觉空间反而用的更多了。。。用空间换遍历的速度吗】 ### 用二叉树表示树、森林 #### 树 =》 二叉树 ![image-20191014172832123](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xuxauh2bj31210u0wuo.jpg) #### 二叉树 =》树 ![image-20191014173159168](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xv0vym5dj311k0u0nes.jpg) #### 二叉树 =》森林 ![image-20191014173228995](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xv1ep9tgj310p0u0at1.jpg) ### 霍夫曼树、霍夫曼编码 把学生成绩归入优良中差。 如果是从优到差一步步判断，可能效果不是很好，因为多数人集中在“中”和“良”。这就需要多次判断才能达到。 ![image-20191014174038846](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xv9xtj4xj31ii0jwajf.jpg) #### 带权路径长度 * 从根节点到目标节点经过的节点数（路径长度） * 走到这个节点的概率/所占比例 加权和就是WPL ![image-20191014180932190](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xw3ykzk7j31j60swgvz.jpg) ![image-20191014180941404](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xw444birj315603mdi4.jpg) #### 构造霍夫曼树方法 目标是树两边概率要接近。以此来减少判断的次数。 方法是，概率从小到大排列。取概率最低的组成一颗小的左右子树，然后把总概率作为节点，放进概率排列中。 以此类推，最终得出整棵树 ![image-20191014181902433](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xwducx8tj30nc0ke42z.jpg) #### 霍夫曼编码 字母、汉字出现的频率是不同的。 高频字符应该用更短的编码，低频字符用更长的编码，以此来节约总编码长度。 假设一共有这些数字，然后根据频率构成霍夫曼树： ![image-20191014182038104](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xwfhwv3kj31k00km134.jpg) 左0右1，得到每个字符的编码。 完成编码和解码需要两个条件： 1. 任何字符的编码，不能是另一个字符编码的前缀。 如1001和10会混淆。 2. 双方要用同一套霍夫曼树 解码的时候就顺着根节点去找，找到了就输出字符，然后顺着编码继续从根节点找 比如100101，解码就是ba ![image-20191014182404911](https://tva1.sinaimg.cn/large/006y8mN6gy1g7xwj2w6svj31ju0k8tix.jpg) ## 第七章 图 图的顶点不能为空。任意两个顶点的逻辑关系，用 边 来表示 ![image-20191017154618435](https://tva1.sinaimg.cn/large/006y8mN6gy1g818ublmm8j314i0u0hdt.jpg) ### 图的存储结构 * 邻接矩阵 顶点用一维数组。边或弧用二维数组来存，即一个矩阵。 ![image-20191017155643703](https://tva1.sinaimg.cn/large/006y8mN6gy1g8194pdlamj31dk0ksk07.jpg) 无向图的边数组是一个对称矩阵 ![image-20191017155803075](https://tva1.sinaimg.cn/large/006y8mN6gy1g81963d7m3j31h80oq13d.jpg) ![image-20191017160248870](https://tva1.sinaimg.cn/large/006y8mN6gy1g819b1b23jj31cs0o6tix.jpg) * 邻接表 如果边少，那么用这个就有点浪费 用数组和链表相结合的方法 ![image-20191017161100817](https://tva1.sinaimg.cn/large/006y8mN6gy1g819jkfculj31nm0ia7fp.jpg) ![image-20191017161048810](https://tva1.sinaimg.cn/large/006y8mN6gy1g819je3urcj31cq0kgwne.jpg) 这记录的都是从节点出去的弧。也可以专门建立一个表，放节点进去的弧 正反结合起来就是十字链表 #### 图的遍历 * 深度优先 就是树的前序遍历 ![image-20191017162826218](https://tva1.sinaimg.cn/large/006y8mN6gy1g81a1pcxlqj31bd0u04ei.jpg) * 广度优先 ![image-20191017163404209](https://tva1.sinaimg.cn/large/006y8mN6gy1g81a7kkd2jj30xp0u07sb.jpg) ### 最小生成树 构造联通网的最小代价生成的树 * prim普里姆算法： 某个顶点为起点，逐步找各个顶点最小成本的边来构建最小生成树。【有点像贪心算法】 ### 最短路径 两顶点之间经过的边上权值之和最少的路径 #### 迪杰斯特拉Dijkstra算法 一步步求出到各个顶点之间最短路径 ![image-20191021140856314](https://tva1.sinaimg.cn/large/006y8mN6gy1g85shs1palj30s60fk78w.jpg) #### 弗洛伊德Floyd算法 先有一个直接跑过去的矩阵。如果从a到b绕一下的成本更小，就把成本更小的路径替换掉原来的路径。 ![image-20191021140816556](https://tva1.sinaimg.cn/large/006y8mN6gy1g85sh68i14j31j80pqk4u.jpg) 感觉就是一个迭代的过程 ### 拓扑排序 有一堆任务，互相有关联，如何选择先做啥后做啥呢？ ![image-20191021141546736](https://tva1.sinaimg.cn/large/006y8mN6gy1g85soweo0aj31g20rsqmj.jpg) 拓扑排序，就是把这个坍缩成一个有先后顺序的链表，然后一个个跟着做就行了。 * 把没依赖的push进栈 * pop栈，把pop出的内容变成孤儿。需要它的节点变成不需要它 * 然后重新看谁没依赖，再push进去，以此往复 ![image-20191021141924695](https://tva1.sinaimg.cn/large/006y8mN6gy1g85ssnyiiqj31640ioqbb.jpg) ### 关键路径 一堆任务有优先级，有依赖。怎么看最长需要时间。 ![image-20191021142501875](https://tva1.sinaimg.cn/large/006y8mN6gy1g85syih7cej317s0icthr.jpg) 感觉类似于求最短路径，不过是变成求最长 ![image-20191021142441822](https://tva1.sinaimg.cn/large/006y8mN6gy1g85sy5xrsqj31ga0h8wpg.jpg) ## 第八章 查找 * 静态查找：就在表里面找 * 动态查找：找不到做点动作，比如找不到就插入；或者查到删除 ### 顺序表查找 排列整齐，构成线性表，进行查找。 #### 顺序查找 就从头到尾一个个匹配 优化方法，是把a\[0]设置为要找的key，然后从后往前找 ![image-20191021144351396](https://tva1.sinaimg.cn/large/006y8mN6gy1g85ti432r7j31580jk4i2.jpg) 这样一次匹配就行了，不用每次i都要和n匹配一下 也可以把常用的放在前面，提高查找的效率。 ### 有序表查找 先做好排列，比如根据拼音顺序排列，这样找起来方便 * 二分查找，就很快。 * 插值查找，就根据要找的东西靠近哪里，就先在哪里找起来。比如a打头的就在前面找。 ![image-20191021144738277](https://tva1.sinaimg.cn/large/006y8mN6gy1g85tm1mg8hj30y605kmzw.jpg) 根据查找关键字，与表中最大最小记录关键字比较后查找。 中间那个是插值计算公式 * 斐波纳切查找 ![image-20191021145021599](https://github.com/joeyZhouYicheng/notes/tree/2876bad0216a7a05e7fcbe85cf58f8f45210350d/Library/Application%20Support/typora-user-images/image-20191021145021599.png) 计算更加简单，大部分情况比二分要好。 ### 索引 数据结构目的是提高数据的处理速度。 索引，把关键字与他对应的记录相关联的过程。 比如用小本子记下重要的东西放在了哪里。需要用的时候看这个小本子就行了。 > 线性索引、树形索引、多级索引 线性就是把索引项集合成一个线性的索引表。 线性索引可分：稠密索引、分块索引、倒排索引 #### 稠密索引 数据的每个记录都对应一个索引项 索引要根据关键码有序排列 【就是目录咯。。】 #### 分块索引 图书馆的藏书。分块放。每一块再建立一个索引项。 > 块间有序，块内无序。 换言之只用排序块与块之间。块内就不用管，节约一下排序的成本。 每块的索引： * 存最大值 * 块个数 * 首个元素的地址 【感觉就是分解了一下查找的任务。。】 #### 倒排索引 比如搜索引擎搜索。 维护一个有序的单词表。找的时候就直接找这个单词表，再跳转到对应的网址 优点是查找非常快，但维护起来很麻烦。尤其多个网站都有同一个关键字 优化方法： * 文章编号可以用增量，记录差值 * 关键字也可以记录差值 * 一次搜索只展示其中的10条 ### 二叉排序树 插入和查找同样高效 左边节点都小，右边节点都大 ### 平衡二叉树 左子树和右子树高度差最多为1 ![image-20191021151955112](https://tva1.sinaimg.cn/large/006y8mN6gy1g85ujo4lhpj31lg0he120.jpg) * 最小不平衡子树 ![image-20191021152052426](https://tva1.sinaimg.cn/large/006y8mN6gy1g85uklz57dj30x60imgsb.jpg) 从这个节点开始不平衡了。 #### 原理 插入时，先检查会不会破坏平衡，如果是，就找到最小不平衡子树，对其进行旋转等操作，使其平衡。 ![image-20191021152255508](https://tva1.sinaimg.cn/large/006y8mN6gy1g85umrjmxcj30rc0km78e.jpg) 这个数字是bf值，就是衡量左右子树的差距。 bf=1就右旋，bf=-1就左旋。这需要从下往上转。 ![image-20191021152844597](https://tva1.sinaimg.cn/large/006y8mN6gy1g85ustdfrjj30u60ka102.jpg) ![image-20191021152401807](https://tva1.sinaimg.cn/large/006y8mN6gy1g85unwqhsej311u0fqdlx.jpg) 旋转后要重新排列3这个节点 ### 多路查找树(B树) 如果硬盘和内存差距很大，那么访问时间不仅仅是查找元素的时间，还要考虑 访问时间 和 会有多少次单独访问。 因此要降低对外存设备的访问次数。也就是让树越扁越好，因此一次就读区一层。 一个节点只存一个元素，或只有两个子树。数据量大的时候就需要多次读取外存。 > 多路查找树，每个节点子树可以有多个，每个节点也能存多个元素 其中四种：2-3树、2-3-4树、B树、B+树 #### 2-3树 每个节点可以有一个2节点的孩子，也可以有一个3节点的孩子。 * 2节点，一个元素+0或2个孩子。很像二叉树，但要么没孩子，要么有两个。 * 3节点，两个元素和三个孩子。也是0或3个孩子。左到右，小中大 【换言之就是把每个节点扩容，最多可以放两个元素】 ![image-20191021160806135](https://tva1.sinaimg.cn/large/006y8mN6gy1g85vxrrl6sj31pk0r4tol.jpg) **2-3树插入和删除** * 2节点插一个变3节点 ![image-20191021161011577](https://tva1.sinaimg.cn/large/006y8mN6gy1g85vzxyjfkj31lo0b87cw.jpg) * 3节点插一个，要把整个相关的树都打乱重排 ![image-20191021161129075](https://tva1.sinaimg.cn/large/006y8mN6gy1g85w1a8969j31m40bgn5c.jpg) ![image-20191021161425401](https://tva1.sinaimg.cn/large/006y8mN6gy1g85w4c7uctj31l80c4aj6.jpg) * 删一个也要重排 ![image-20191021161638672](https://github.com/joeyZhouYicheng/notes/tree/2876bad0216a7a05e7fcbe85cf58f8f45210350d/Library/Application%20Support/typora-user-images/image-20191021161638672.png) #### 2-3-4树 扩展2-3树，一个节点最多放三个元素和四个孩子 也是插入和删除会导致结构重排 ![image-20191021162227142](https://tva1.sinaimg.cn/large/006y8mN6gy1g85wcoqzozj314o0badk7.jpg) #### B树 2-3树和2-3-4树都是B树的特例 节点最大的孩子树，是B树的阶。3阶、4阶B树 比如根节点1001阶有1000个元素，可以存10亿元素。因此只需把根节点留在内存，只需要最多读两次硬盘就能获取某个关键字。 即每次磁盘访问都要获得最大数据量。 #### B+树 B树遍历比较麻烦，需要在子树和根节点中来回跳。 * 根节点元素会在子树中最后重新出现 * 子树前面会指向后面 ![image-20191021164645522](https://tva1.sinaimg.cn/large/006y8mN6gy1g85x1z9oxhj311m0e6aee.jpg) 分支节点只是索引，不存特定内容。顺序查找就直接从左往右查即可。 更适合有范围的查找。 ### 散列表/哈希表查找 不用比较下标大小，直接通过关键字来查找记录内存的存储位置。 散列技术：存储位置和关键字之间建立一个对应关系。换言之，输入关键字，就能输出对应存储位置。 函数叫 散列函数/哈希函数。连续存储空间叫 散列表或哈希表。 存储地址都是用哈希函数算出来的。 【感觉类似于用哈希函数编码和解码】 * 适合一一对应的精确查找。 * 不适合范围查找、结果多条等查找。 #### 散列函数的构造 希望这个函数：计算简单、冲突少。地址分布均匀。 * 根据关键字规律 * 抽取关键字差异 * 平方取中间三位。适合不知道分布，且位数不大的情况 * 三位一组，加起来取后三位 * 求余数 * 随机数 #### 处理冲突 有冲突就再找地址。 * 线性 ![image-20191021170231193](https://tva1.sinaimg.cn/large/006y8mN6gy1g85xidnwtsj31b404mjvj.jpg) * 平方运算 ![image-20191021170341614](https://tva1.sinaimg.cn/large/006y8mN6gy1g85xjlqowuj31hg03agph.jpg) * 随机数 * 准备多个散列函数，一个不行换一个 * 不换地方，有冲突就增加链表长度 ![image-20191021170511259](https://tva1.sinaimg.cn/large/006y8mN6gy1g85xl5tdbkj30ok0akju0.jpg) * 专门找个地方放冲突的数 ## 第九章 排序 * 稳定性：如果两个值相等，那么排序前在前的，排序后也要再前面 * 内排序：排序过程中，全部记录放在内存中； 外排序：需要放一点东西在外存，排序时还要交换数据 内排序：插入、交换、选择、归并 ### 冒泡排序 拿着一个数，遇到比它大的就交换位置，就从下往上不断冒泡就完事了。 但如果只需要排序前几个，那么之后的对比判断就是多余的。可以加一个flag，如果没有交换，就停止排序。 ### 简单选择排序 对每个位置，找到后面的最小值，与当前值进行交换。 ### 直接插入排序 将记录插入到已经排序好的有序表中 ### 希尔排序 先分组排序，让总体来看小的在前，大的在后，然后再插入排序。 大意就是，先粗排，再精排。 需要定一个增量，一开始很大，把两端两个值排序。然后这个增量慢慢缩小为1 ![image-20191022114218305](https://tva1.sinaimg.cn/large/006y8mN6gy1g86tvijp1mj31460rgtln.jpg) ![image-20191022114232859](https://tva1.sinaimg.cn/large/006y8mN6gy1g86tvrijquj314i0e20zi.jpg) ### 堆排序 之前排序，遍历的结果没有保存，因此有重复的劳动。 可以在一次排序过程中，对其他记录做出相应调整，就比较高效。 > 堆：完全二叉树，每个节点值都大于或小于左右孩子。大于叫大顶堆；小于叫小顶堆 > > ![image-20191022114918052](https://tva1.sinaimg.cn/large/006y8mN6gy1g86u2sfcetj31my0hi130.jpg) * 将待排序的序列构造成一个大顶堆 * 根节点即最大值，拿掉。也就是和末尾元素互换。 即把最大值放在序列尾 * 重新排序堆 完全二叉树性质： ![image-20191022135458155](https://tva1.sinaimg.cn/large/006y8mN6gy1g86xpjwutcj315i0oi49p.jpg) 以此来确定子树位置 ![image-20191022135803206](https://tva1.sinaimg.cn/large/006y8mN6gy1g86xsrt96ej31e40u0x3a.jpg) ### 归并排序 两两排序后再合并排序 ![image-20191022135948715](https://tva1.sinaimg.cn/large/006y8mN6gy1g86xulpkaej31ze0lanfa.jpg) ### 快速排序 一次排序把序列分成两部分，一部分全部小于另一部分。再分别进行排序。 每一轮都拿着一个数，叫枢轴，然后排序数组。令其左边的数都比他小，右边都比他大。 方法是双指针，如果左边比右边的大，就交换双方位置 ![image-20191022142119874](https://tva1.sinaimg.cn/large/006y8mN6gy1g86ygz1qorj31bk0bi44h.jpg) ![image-20191022142126482](https://tva1.sinaimg.cn/large/006y8mN6gy1g86yh3dx7wj31do0ckdly.jpg) #### 优化： 总是选取第一个数作为枢轴排序，是不合理的。 我们是希望枢轴是在中间的位置。如果选择的数太小或太大，就没有再拆分的意义了。 * 随机选数 * 选三个数先排序，然后取中间数。一般选左中右，无序的数组不需要再随机选。 * 如果序列非常大，可以选9个数。分三次每次取三个数，三个中数再取中数。 * 优化交换 枢轴备份。交换的过程就写入，而不是真的去交换。low=high的时候再写入 ![image-20191022142937823](https://tva1.sinaimg.cn/large/006y8mN6gy1g86ypm9qp9j311q0bswk1.jpg) ![image-20191022143105240](https://tva1.sinaimg.cn/large/006y8mN6gy1g86yr4qv9tj30zo0a0dk6.jpg) ![image-20191022142944971](https://tva1.sinaimg.cn/large/006y8mN6gy1g86ypqarbkj30zi0bqjx3.jpg) * 小数组还是用直接插入最好。 * 尾递归优化 ![image-20191022144215944](https://tva1.sinaimg.cn/large/006y8mN6gy1g86z2snpxjj31l80tc1kx.jpg) ![WechatIMG39](https://tva1.sinaimg.cn/large/006y8mN6gy1g8731y4th1j30tz1sogph.jpg)