《2022年数据结构知识点总结整理资料 .docx》由会员分享，可在线阅读，更多相关《2022年数据结构知识点总结整理资料 .docx（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品_精品资料_数据结构学问点总结整理资料数据结 构知 识点 总结 整理0 、常考基础必知必会A. 排序: 排序有几种 , 各种排序的比较 , 哪些排序是稳固的 , 快排的算法;B. 查找: 哈希查找、二叉树查找、折半查找的对比, 哈希映射和哈希表的区分 .C. 链表和数组的区分 , 在什么情形下用链表什么情形下用数组 .D. 栈和队列的区分 .E. 多态, 举例说明 ;overload和 override的区分.F. 字符串有关的函数 , 比如让你写一个拷贝字符串的函数啊 , 或者字符串反转啊什么的. strcpy和 memcpy.G. 继承、多继承 .H. 面对对象有什么好处 .I. 说说
2、 static的与众不同之处, 假如一个变量被声明为static,它会被安排在哪里 .在什么时候安排空间等 .J. 什么是虚函数、纯虚函数、虚的析构函数, 用途.K. 内存泄漏及解决方法 .可编辑资料 - - - 欢迎下载精品_精品资料_网络部分 :OSI 模型 7层结构,TCP/IP模型结构 .B. TCP/UDP 区分.C. TCP 建立连接的步骤 .D. 香农定理 .1 、二叉树三种遍历的非递归算法 背诵版 本贴给出二叉树先序、中序、后序三种遍历的非递归算法 , 此三个算法可视为标准算法 ,直接用于考研答题.1. 先序遍 历非递 归算法#define size 100 typedef s
3、tructBitree Elemsize;int top; SqStack;void PreOrderUnrecBitree tSqStack s;StackInits;pt;whilep.null | .StackEmptys while p.null/ 遍 历 左 子 树 visitep-data;pushs,p; pp-lchild; /endwhile if .StackEmptys / 通过下一次循环中的内 嵌 while 实 现 右 子 树 遍 历 ppops; pp-rchild;/endif/endwhile/PreOrderUnrec2. 中序遍 历非递 归算法#define
4、 size 100 typedef struct可编辑资料 - - - 欢迎下载精品_精品资料_Bitree Elemsize;int top; SqStack;void InOrderUnrecBitree tSqStack s;StackInits;pt;whilep.null | .StackEmptys while p.null/ 遍历左子树 pushs,p; pp-lchild; /endwhileif.StackEmptysppops;visitep-data;/访 问 根 结 点pp-rchild;/通 过 下 一 次 循 环 实 现 右 子 树 遍 历/endif/endwhi
5、le/InOrderUnrec3. 后序遍 历非递 归算法#define size 100typedef enumL,R tagtype;typedef structBitree ptr;tagtype tag; stacknode;typedef structstacknode Elemsize;int top; SqStack;/ 后序遍历void PostOrderUnrecBitree tSqStack s;stacknode x;StackInits;pt; do whilep.null / 遍历左子树 x.ptr p;x.tag L; /标记为左子树 pushs,x; pp-lch
6、ild; while .StackEmptys &s.Elems.top.tagR x pops;可编辑资料 - - - 欢迎下载精品_精品资料_p x.ptr; visitep-data;/tag为 R, 表示右子树拜访完毕 , 故拜访根结点 if .StackEmptys s.Elems.top.tag R; /遍历右子树 ps.Elems.top.ptr-rchild; while .StackEmptys;/PostOrderUnrec4. 层次遍 历算法/二叉树的数据结构structBinaryTreeint value; /不写模板了 , 临时用整形代替节点的数据类型BinaryT
7、ree *left;BinaryTree *right;BinaryTree*root; /已知二叉树的根节点/层次 遍历voidLevel const BinaryTree *rootQueue *bufnew Queue; /定义一个空队列 , 假设此队列的节点数据类型也是整形的 BinaryTreet;/一个临时变量 buf.push_backroot;/令根节 点 入 队 whilebuf.emptyfalse/当 队 列 不 为 空 p buf.front;/取出队列的第一个元素 coutp-value;ifp-left.NULL/如左子树不空, 就令其入队q.push p-left
8、 ; ifp-right. NULL/如右子树不空 , 就令其入队 q.pushp-right; buf.pop; /遍历过的节点出队 coutendl;2 、线性表可编辑资料 - - - 欢迎下载精品_精品资料_(1) 性表的链式储备方式及以下几种常用链表的特点和运算: 单链表、循环链表 , 双向链表 ,双向循环链表.(2) 单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式.(3) 单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引储备结构的各自好处.3 、栈与队列你可以问一下自己是不是已经知道了以下几点 :1 栈、队列的定义及
9、其相关数据结构的概念 , 包括: 次序 栈, 链栈, 共 享栈, 循环队列,链队等.栈与队列存取数据 请留意包括 : 存和取两部分 的特点.2 递归算法. 栈与递归的关系 , 以及借助栈将递归转向于非递归的经典算法 : n. 阶乘问题 ,fib数列问题 ,hanoi问题 ,背包问题 ,二叉树 的递归 和非递归 遍历问 题,图的 深 度遍历与 栈的关系等.其中, 涉及到树与图的问题 , 多半会在树与图的相关章节中进行考查. 3 栈的应用 : 数 值表 达式的求 解, 括 号的配 对等的原理, 只作原理性明白 , 详细要求考查此为题目的算法设计题不多. 4 循环队列中判队空、队满条件 ,可编辑资料
10、 - - - 欢迎下载精品_精品资料_循环队列中入队与出队 循环队列在插入时也要判定其是否已满 , 删除时要判定其是否已空 算法. 【循环队列的队空队满条件 为了便利起见 , 商定: 初始化建空队时 , 令 frontrear0,当队空时 :frontrear,当队满时 :frontrear亦成立 ,因此只凭等式frontrear无法判定队空仍是队满.有两种方法处理上述问题 :1 另设一个标志位以区分队列是空仍是满. 2 少用一个元素空间 , 商定以“队列头指针 front在队尾指针 rear的下一个位置上”作为队列“满”状态的标志. 队空时 : frontrear , 队满时 : rear+
11、1%sizefront 】 假如你已经对上面的几点了如指掌 , 栈与队列一章可以不看书了.留意 , 我说的是可以不看书, 并不是可以不作题哦./循环队列的主要操作 : 1创建循环队列 2 初始化循环队列 3 判定循环队列是否为空 4 判定循环队列是否为满 5 入队、出队 /空出头尾之间的一个元素不用#include #include #define SIZE 100 typedef struct intelemSIZE;intfront, rear; Quque; /定义队头 intinitQueQuque *q / 初始化 *q-front0;*q-rear0;int isFullQuque
12、 *qifq-frontq-rear+1%SIZE/判满空出一个元素不 用 刘勉刚 return1; else return0; intinsertQueQuque *q,int elemifisFull*qreturn-1;*q-elem*q-rearelem;*q-rear*q-rear+1%SIZE;/插入 return0; int isEmptyQuque *q可编辑资料 - - - 欢迎下载精品_精品资料_ifq-frontq-rear/判 空return1;elsereturn0;int deleteQueQuque*q,int*pelemifisEmpty*qreturn0;*p
13、elem*q-elem*q-front; *q-front*q-front +1%SIZE; return0;4 、串串一章需要攻破的主要堡垒有:1. 串的基本概念 , 串与线性表的关系 串 是其元 素均 为字符型 数据的 特殊线 性表, 空串与空格串的区分 , 串相等的条件 ;2. 串的基本操作 , 以及这些基本函数的使用 , 包括:取子串 ,串连接, 串替 换,求串长等等.运用串的 基本操 作去完 成特 定的算法是许多学校在基本操作上的考查重点. 3.次序串与链串及块 链串的区分和联系 , 实现方式.4. KMP 算法思想. KMP 中 next数组以及 nextval数组的求法. 明确传
14、统模式匹配算法的不足 ,明确 next数组需要改进.可能进行的考查方式是: 求 next和nextval数组值, 依据求得的 next或 nextval数组值给出运用 KMP 算法进行匹配的匹配过程.5 、多维数组和广义表矩阵包括 : 对称 矩阵,三角 矩阵, 具有某种 特点的 稀疏 矩阵等.熟识稀疏矩阵的三种不同储备方式 :三元组, 带辅 助行 向量的可编辑资料 - - - 欢迎下载精品_精品资料_二 元组,十字链 表储备.把握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法.6 、树与二叉树树一章的学问点包括 : 二叉树的概念、性质和储备结构 , 二叉 树遍历 的三 种算法递归与 非递归
15、 ,在三种基本遍历算法的基础上实现二叉树的其它算法,线索二 叉树的概念和 线索化 算法以及线 索化后的 查找算法,最优二 叉树的概念、构成和应用 , 树的概念和储备形式 ,树与森林的遍历算法及其与二叉树遍历算法的联系 , 树 与森 林和二叉 树的转 换.1 二叉树的概念、性质和储备结构考查方法可有 :直接考查二叉树的定义 ,让你说明二叉树与一般双分支树左右子树无序的区分 ;考查满二 叉树和 完全二 叉树的性质 ,一般二 叉树的 五个性质:A. 第 i层的最多结点数 ,B. 深度为 k的二叉树的最多结点数 ,C. n0n2+1 的性质,D.n 个结点的完全二叉树的深度 ,E.次序储备二叉树时孩子
16、结点与父结点之间的换算关系root从 1开头, 就左为:2*i,右为: 2*i+1 .可编辑资料 - - - 欢迎下载精品_精品资料_二叉树的 次序存 储和二 叉链 表储备的各自优 缺点及适用场合, 二叉树的 三叉链 表表示方法. 2 二叉树的三种遍 历 算法这一学问点把握的好坏 , 将直接关系到树一章的算法能否懂得 , 进而关系到树一章的算法设计题能否顺当完成.二叉树的遍历算法有三种 : 先序 , 中序和后序.其划分的依据是视其每个算法中对 根结点 数据的 拜访 次序而定.不仅要娴熟把握三种遍历的递归算法 , 懂得其执行的实际步骤, 并且应当 娴熟掌 握三 种遍历的 非递归 算法.由于二叉树
17、一章的许多算法 , 可以直接依据三种递归算法改造而来 比如: 求叶子个数 , 所以, 把握了三种遍历的非递归算法后 , 应付诸如 :“利用非递归算法求二叉树叶子个数” 这样的题目就下笔如有神了.3 可在三种遍历算法的基础上改造完成的其它二 叉树算法 : 求叶子个数 , 求二叉树 结点总数 , 求度为 1或度 为 2的结点 总数, 复制二 叉 树, 建立 二叉树, 交换 左右子 树, 查找值为n 的某个指 定结点, 删除 值为 n的某个 指定结 点, 诸如此类等等等等. 假如你可以娴熟把握二叉树的递归和非递归遍历算法 , 那么解决以上问题就是小菜一碟了. 4 线索二叉树 : 线索二叉树的引出,
18、是 为防止如 二叉树 遍历时 的递 归求解.众所周知 , 递归虽然可编辑资料 - - - 欢迎下载精品_精品资料_形式上比较好懂得 , 但是消耗了大量的内存资源 , 假如递归层次一多 , 势必带来资源耗尽的危急 , 为了避免此类情形 , 线索二叉树便堂而皇之的显现了. 对于线索二叉树 ,应当把握 :线索 化的实质 ,三种线索化 的算法 ,线 索化后 二叉树的遍历算 法, 基本线索二叉树的其它算法问题 如:查 找某一类线索二 叉树中 指定结 点的 前驱或后 继结点就是一类常考题 .5 最优二叉树 哈 夫 曼树: 最优二叉树是为明白决特定问题引出的特殊二叉树结构 , 它的前提是给二叉树的每条边赋予
19、了权值 , 这样 形成的 二叉 树按权相 加之和 是最小 的.最优二叉树一节 , 直接考查算法源码的很少, 一般是给你一组数据 , 要求你建立基于这组数据的最优二叉树, 并求出其最小权值之和 , 此类题目不难 , 属送分题. 6 树与森林 : 二叉树是一种特殊的树,这种特殊不仅仅在于 其分 支最多为 2以及其它特点 , 一个最重要的特殊之处是在于 :二叉树 是有序的 . 即:二叉 树的左 右孩子是 不行交 换的 ,假如 交换了就 成了另外一棵 二叉树.树与森林的遍 历, 不像二叉树那样丰富 ,他们只 有两种 遍历算法 :先 根与后根 对于森 林而言 称作:先序与后 序遍历 .此二者的先根与 后
20、根遍 历与二 叉树 中的遍历算法可编辑资料 - - - 欢迎下载精品_精品资料_是有对应关系的 : 先 根遍历 对应二叉 树的先 序遍历 , 而后根遍历 对应二 叉树的 中序 遍历. 二叉树 、树与森林 之所以 能有以 上的 对应关系 ,全 拜二叉 链表所赐. 二 叉树使 用二叉 链表分 别存放他 的左右孩子 , 树利 用二叉 链表存 储孩子及 兄弟 称孩 子兄弟链表 , 而森 林也是 利用二 叉链表存 储孩子及兄弟 . 7 、图 1. 图的基本概念 : 图的定义和特点 , 无向 图, 有 向图, 入度, 出度, 完全图, 生 成子图, 路径长度, 回路, 强 连 通图, 强 连通分 量等概念
21、.2. 图的几种储备形式 : 邻接矩 阵, 逆 邻接 表, 十字链 表及 邻接多 重表.在考查时 , 有的学校是给出一种储备形式 ,要求考生用算法或手写出与给定的结构相对应的该图的另一种储备形式.3.考查图的两种遍历算法 : 深 度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法, 这两个算法对图一章的重要性等同于“先序、中序、后序遍历” 对于二叉树一章的重要性. 在考查时 ,图一章的算法设计题常常是基于这两种基本的遍历算法而设计的 , 比如:“求最 长的 最短路径问题”和“判 断两 顶点间是 否存在长为 K 的简洁 路径问 题”, 就分别用到了广度遍历和深度遍历算法. 4.生成树、最
22、小 生成 树的概念以及最 小生成 树的 构可编辑资料 - - - 欢迎下载精品_精品资料_造:PRIM 算法和 KRUSKAL算法.考查时 , 一般不要求写出算法源码 ,而是要求依据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树. 5. 拓扑排序问题 : 拓扑排序有两种方法 , 一是无前 趋的顶 点优先算法 , 二是无 后继的 顶点优先算法.换句话说, 一种是“从前向后”的排序 , 一种是“从后向前”排.当然 ,后一种排序出来的结果是“逆拓扑有序”的.6.关键路径问题 : 这个问题是图一章的难点问题.懂得关键路径的关键有三个方面 :一是何谓 关键路 径;二是最早 时间是什么意思
23、、如何求 ;三是最晚 时间是什么意思、如何求.简洁的说 , 最早时间是通过 “从前向后” 的方法求的 , 而最晚时间是通过“从后向前”的方法求解的, 并且, 要想求最晚时间必需是在全部的最早时间都已经求出来之后才能进行.在实际设计关键路径的算法时, 仍应当留意以下这一点: 采 用邻接 表的存 储结 构, 求最 早时间和最 晚时间 要采纳 不同 的处理方 法,即 :在算 法初始时,应 该第一 将全部 顶点 的最早时 间全部置为 0.关键路径问题是工程进度掌握的重要方法, 具有很强的有用性.7.最短路径问题 : 与关键路径问题并称为图一章的两只拦路虎. 概念 懂得是比 较简洁 的,关 键是 算法的
24、理 解.可编辑资料 - - - 欢迎下载精品_精品资料_最短路径问题分为两种 : 一是求从某一点出 发到其 余各 点的最短 路径 单源最短路径 ; 二是求图中每一 对顶点 之间的 最短 路径.这个问题也具有特别有用的背景特色 , 一个典型的应当就是旅游景点及 旅行路 线的选 择问题.解决第一个问题用 DIJSKTRA算法, 解决其次个问题用 FLOYD算法, 留意区分.8 、查找 search 先弄清晰以下几个概念 :关 键字、 主关键 字、 次 关键字的含义;静态 查找与 动态查 找的含义及区别; 平均 查找长 度 ASL 的概念及在各种查找算法中的运算方法和运算结果 , 特殊是一些典型结构
25、的 ASL 值, 应当记住.一般将 search分为三类 : 在次序表 上的查 找; 在 树表 上的查找; 在哈 希表上 的查 找.1线性表上的查找 : 主要分为三种线性 结构:次序表 .传统查找方法 : 逐个比较 ;有序次序 表.二分查找法 留意适 用条件以及其递归 实现方法 ;索引次序 表.对索引结构 , 采纳索引查找算法. 留意这三种表下的 ASL 值以及 三种算法 的实现. 2树表上的查找 : 树表主要分为以下几种 : 二叉排 序树可编辑资料 - - - 欢迎下载精品_精品资料_即二叉 查找 树, 平 衡二叉 查找树 AVL树,B树, 键树.其中, 尤以前两种结构为重 , 也有部分名校
26、偏爱考 B 树的.由于二叉 排 序树与平 衡二叉树是 一种特 殊的二 叉树.二叉排序 树,简言之 ,就是“左小右 大” ,它的 中序遍 历结果是 一个递 增的有 序序 列. 平 衡二叉排序树是 二叉排 序树的 优化 ,其本质 也是一 种二叉 排序树,只不 过,平 衡排序 二叉 树对左右 子树的深度有 了限定:深度之 差 的肯定值 不得大 于 1 .对于二叉排序树 , “判 断某棵 二 叉树是否 二叉排序树”这一算法常常被考到 ,可用递归 ,也可以用非递归. 平衡二叉 树的建 立也是一个常考点 ,但该学问点归根结底仍是关注的平稳二叉树 的四种 调整 算法,调整的 一个参 照是 :调整前后 的中序
27、遍历结 果相同. B树是二叉排序树的进一步改进 , 也可以把B 树理 解为三叉、 四叉.排序树.除 B 树的查找算法外 , 应当特殊留意一下 B 树的插入 和删除算法 , 由于这两种算法涉及到 B 树 结点的分 裂和合并 , 是一个难点.键树keywordtree,又称数字搜寻树digitalsearch tree或字符树. trie树也可说等同于键树或属于键树的一种.键 树特殊适 用于查 找英文 单词 的场合.一般可编辑资料 - - - 欢迎下载精品_精品资料_不要求能完整描述算法源码, 多是依据算法思想建立键树及描述其大致查找过程. 3基于哈希表的查找算法 : 哈希译自“ hash”一词,
28、 意为“散列”或“ 杂凑”.哈希 表查找 的基本 思想是: 依据 当前待查找数 据的特 征,以记 录 关键字为 自变量 ,设计一个function ,该函数对关 键字 进行转换 后,其说明结 果为待 查的的 址.基于哈希表的考查点有 :哈 希函数的 设计,冲突解 决方 法的挑选及冲突处理过 程的描 述.9 、内部排序考查你对书本上的各种排序 算法及其 思想以及其优 缺点和性能指 标 时间复杂度 能否了如指掌.排序方法分类有 : 插入、挑选、交换、归并、计数等五种排序方法. 1插入排序中又可分为 :直接插 入、 折 半插入、2 路插 入 . 、 希尔排序.这几种插入排序算法的最根本的不同点 ,
29、说究竟就是依据 什么规 就查找新 元素的 插入点.直接插入是依次查找, 折半插入是折半查找 , 希尔排序 , 是通过掌握每次参加排序的数的总范畴“由小到大”的增量来实现排序效率提高的目的.2交换排 序, 又称冒泡排序 , 在交换排序的基础上改进又可以得到快速排序.快速排序的思可编辑资料 - - - 欢迎下载精品_精品资料_想, 一语以敝之 : 用中 间数 将待排数 据组一 分为二.3挑选排序可以分为 :简 单挑选、 树挑选、 堆 排序.挑选排序相对于前面几种排序算法来说, 难度大一点.这三种方法的不同点是 , 依据 什么 规章选取最小的 数.简洁挑选 , 是通过简洁的数组遍历方案确定最小数 ;
30、树挑选,是通过“锦标赛” 类似的思想 ,让两数相比 ,不断剔除较大 小者,最终选出最小 大数;而堆排序 , 是利用堆这种数据结构的性质 , 通过堆元素的删除、 调整等一系列操作将最小数选出放在堆顶.堆排序中的堆建 立、堆调 整是重要考点.4归 并排序, 是 通过“ 归并”这 种操作 完成排 序的 目的,既然是归并就必需是两者以上的数据集合才可能实现归并.所以 , 在归并排序中 , 关注 最 多的就是 2 路归并.算法思想比较简洁 ,有一点 , 要牢记在心 : 归并 排序是稳 定排序. 5 基数排序 , 是一种很特殊的排序方法 , 也正是由于它的特殊 , 所以, 基数排序就比较适合于一些特殊的场
31、合 , 比如扑克牌排序问题等. 基数排序 , 又分为 两种:多关键 字的排序 扑克牌排序 , 链式排 序 整 数排序 .基数排序的核心思想可编辑资料 - - - 欢迎下载精品_精品资料_也是 利用“ 基数空 间” 这个概念 将问题规模规 范、变 小, 并 且,在排序的 过程中 , 只要 依据 基排的思 想, 是 不用进 行关 键字比较 的,这样得出的最终序列就是一个有序序列.本章各种排序算法的思 想以及伪 代码实 现, 及其时 间复杂度都是必需把握的./稳 定 性分 析/排序算法的稳固性 , 通俗的讲就是能 保证排 序前 2个 相 等的数其 在序列 的前后 位置 次序和排 序后它们两 个的前
32、后位置 次序 相同.稳固性的 好处:如排 序算法 假如是稳定的 ,那么 从一个键上排序 ,然 后再从 另一个 键上排序 ,第一个键排 序的结 果可以 为第 二个键排 序所用.基数排序就是这样, 先按低位排序 , 逐次按高位排序, 低位相同的元素其次序再高位也相同时是不会转变的.另外,假如排序算法稳固 , 对基于比较的排序算法而言 , 元素交换的次数可能会少一些个人感觉, 没有证明.分析一下常见的排序算法的稳固性 , 每个都给出简洁的理由. 1冒泡排序冒泡排序就是把小的 元素往前 调或者 把大的元素 往后调. 比较是 相邻的 两个 元素比较 ,交换也发生 在这两 个元素 之间 .所以, 假如两个
33、元素相等 , 我想可编辑资料 - - - 欢迎下载精品_精品资料_你是不会再无聊的把他们俩交换一下的; 假如两个相等的元素没有相邻, 那么即使通过前面的两两交换把两个相邻起来 , 这时候也不会交换 , 所以相同元素的前后次序并没有转变, 所以 冒泡排序是一种 稳固排 序算 法. 2挑选排序挑选排序是给每个位置挑选当前元素最小的 , 比如给第一个位置挑选最小的 , 在剩余元素里面给其次个元素挑选其次小的, 依次类推 , 直到第 n-1个元素 ,第 n个元素不用挑选了 , 由于只剩下它一个最大的元素了. 那么, 在一趟挑选 , 假如当前元素比一个元素小 , 而该小的元素又显现在一个和当前元素相等的
34、元素后面, 那么交换后稳固性就被破坏了.比较拗口 , 举个例子 ,序列 5 8 5 2 9 , 我 们知道 第一遍选 择第 1 个 元素 5 会和2 交换, 那么原 序列中 2 个 5 的相对前后次序 就被破 坏了, 所以 挑选排序 不是一 个稳固 的排 序算法. 3 插入排序 插入排序是在一 个已 经有序的 小序列 的基础 上, 一次插入 一个元素.当然 , 刚开头这个有序的小序列只有 1 个元素, 就是第一个元素. 比较是从有序序列的末尾开头 , 也就是想要插入的元素和已经有序的最大者开头比起 , 假如比它大就直接插入在其后面, 否就始终往前找直到找到它该插入的位置. 假如碰 见一个和 插
35、入元 素相等 的, 那可编辑资料 - - - 欢迎下载精品_精品资料_么插入 元素把 想插入 的元 素放在相 等元素的后面.所以,相等元素的前后次序没有转变 ,从原无序序列出去的次序就是排好序后的次序 ,所以插入 排序是 稳固的. 4快速排序快速排序有两个方向 ,左边的 i下标始终往右走 , 当 ai acenter_index,其中center_index是中枢元素的数组下标 ,一般取为数组第 0个元素. 而右边的 j下标始终往左走 ,当 ajacenter_index.假如 i和 j都走不动了 ,i j,交换 ai和 aj,重复上面的过程 , 直到 ij.交换 aj和 acenter_in
36、dex,完成一趟快速排序.在中枢元素和 aj交换的时候 , 很有可能把前面的元素的稳固性打乱 , 比如序列为 5 3 3 4 3 8 9 1011, 现在中枢元素 5和 3 第 5个元素 , 下标从 1开头计交换就会把元素3的稳固性打乱 , 所以快速 排序是 一个 不稳固的 排序算法, 不 稳固发 生在中 枢元 素和 aj交换的 时刻. 5归并排序归并排序是把序列递归的分成短序列,递归出口是短序列只有 1个元素认为直接有序或者 2个序列 1 次比较和交换 , 然后把各个有序的段序列合并成一个有序的长序列 , 不断合并直到原序列全部排好序. 可以发觉 , 在 1个或 2个元素时 ,1个元素不会交
37、换,2个元素假如大小相等也可编辑资料 - - - 欢迎下载精品_精品资料_没有人有意交换 , 这不会破坏稳固性. 那么, 在短的有序序列合并的过程中 , 稳固是是否受到破坏.没有, 合并过程中我们可以保证假如两个当前元素相等时 , 我们把处在前面的序列的元素保存在结果序列的前面 , 这样就保证了稳固性. 所以, 归并排序也是稳固的排序算法. 6 基数排序 基数排序是依据低位先排序 , 然后收集; 再依据高位排序 , 然后再收集 ; 依次类推 , 直到最高位.有时候有些属性是有优先级次序的 , 先按低优先级排序 ,再按高优先级排序 , 最终的次序就是高优先级高的在前 , 高优先级相同的低优先级高
38、的在前.基数排 序基于 分别排 序, 分 别收集 ,所以其是 稳固的 排序算 法. 7 希尔排序 shell 希尔排序是依据不同步长对元素进行插入排序 , 当刚开头元素很无序的时候 , 步长最大, 所以插入排序的元素个数很少 , 速度很快 ; 当元素基本有序了 , 步长很 小,插 入排序 对于有序 的序列效率很 高.所以 , 希尔排序的时间复杂度会比 on2 好一些.由于多次插入排序 , 我们知道一次插入排序是稳固的 , 不会转变相同元素的相对次序, 但在不同的插入排序过程中 , 相同的元素可能在各自的插入排序中移动, 最终其稳固性就会被打乱 , 所以 shell排序是不 稳固的. 8堆排序我
39、们知道堆的结构是节点可编辑资料 - - - 欢迎下载精品_精品资料_i的孩子为 2*i和 2*i+1节点,大顶堆要求父节点大于等于其2个子节点, 小顶堆要求父节点小于等于其 2个子节点.在一个长为 n的序列, 堆排序的过程是从第n/2开头和其子节点共 3个值挑选最大大顶堆或者最小小顶堆 ,这 3个元素之间的挑选当然不会破坏稳固性.但当为 n /2-1,n/2-2,.1这些个父节点挑选元素时, 就会破坏稳固性.有可能第 n/2个父节点交换把后面一个元素交换过去了, 而第 n/2-1个父节点把后面一个相同的元素没有交换 , 那么这 2个相同的元素之间的稳固性就被破坏了. 所以, 堆 排序不 是稳
40、定的排序 算法./冒泡排序插 入排序 二 路 插入排序 希 尔排序快速排序挑选排 序 归并排 序 堆排序算法的C/C+实现/可编辑资料 - - - 欢迎下载精品_精品资料_/#includeusing namespace std;/ 交换两个数的值void swapint &a,int &b int tmp;tmpa;ab;btmp;/ 屏幕输出数组void displayint array,int lencouttheresultis:endl;forinti0;ilen;i+ coutarrayi ;coutendl;/*冒泡排序算法思想 : 将被排序的记录数组R1.n垂直排列 , 每个记
41、录Ri 看作是重量为 Ri.key的气泡.依据轻气泡不能在重气泡之下的原就, 从下往上扫描数组 R: 凡扫描到违反本原就的轻气泡 , 就使其向上 飘浮 .如此反复进行 , 直到最终任何两个气泡都是轻者在上, 重者在下为止.时间复杂度 on2 空间复杂度 o1 比较次数 nn+1/2*/void bubble_sortint array,int lenforintilen-1;i0;i-forintj0;ji;j+可编辑资料 - - - 欢迎下载精品_精品资料_ifarrayjarrayj+1swaparrayj,arrayj+1;/*直接插入排序算法思想 : 把 n个待排序的元素看成为一个有序表和一个无序表, 开头时有序表中只包含一个元素, 无序表中包含有 n-1个元素, 排序过程中每次从无序表中取出第一个元素 , 将它插入到有序表中的适当位置, 使之成为新的有序表, 重复 n-1次可完成排序过程.时间复杂度 on2 空间复杂度 o1 比较次数 nn+1/2*/void insert_sortint array,int lenint tmp,i,j;fori 1;i len;i+ if arrayi arrayi-1tmparrayi;arrayiarrayi-1;/插入到相 应位置for ji-2;