程序员软考专用复习预习资料.doc

《程序员软考专用复习预习资料.doc》由会员分享，可在线阅读，更多相关《程序员软考专用复习预习资料.doc（193页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、|常考基础必知必会 A. 排序： 排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法; B. 查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别?C. 链表和数组的区别，在什么情况下用链表什么情况下用数组?D. 栈和队列的区别?E. 多态，举例说明;overload 和 override 的区别?F. 字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么 的。strcpy 和 memcpy?G. 继承、多继承?H. 面向对象有什么好处?I. 说说 static 的与众不同之处，如果一个变量被声明为 static，它会被分配在哪里?在什 么时候分配空间等

2、?J. 什么是虚函数、纯虚函数、虚的析构函数，用途?K. 内存泄漏及解决方法?网络部分：OSI 模型 7 层结构，TCP/IP 模型结构?B. TCP/UDP 区别?|C. TCP 建立连接的步骤?D. 香农定理? 二叉树三种遍历的非递归算法(背诵版)1.先序遍历非递归算法 #define maxsize 100 typedef struct Bitree Elemmaxsize;int top; SqStack; void PreOrderUnrec(Bitree t) SqStack s;StackInit(s);p=t;while (p!=null | !StackEmpty(s)whi

3、le (p!=null) /遍历左子树visite(p-data);push(s,p);p=p-lchild; |/endwhileif (!StackEmpty(s) /通过下一次循环中的内嵌 while 实现右子树遍历p=pop(s);p=p-rchild; /endif /endwhile /PreOrderUnrec 2.中序遍历非递归算法 #define maxsize 100 typedef struct Bitree Elemmaxsize;int top; SqStack; void InOrderUnrec(Bitree t) SqStack s;StackInit(s);p

4、=t;while (p!=null | !StackEmpty(s)|while (p!=null) /遍历左子树push(s,p);p=p-lchild;/endwhileif (!StackEmpty(s)p=pop(s);visite(p-data); / 访问根结点p=p-rchild; /通过下一次循环实现右子树遍历/endif /endwhile /InOrderUnrec 3.后序遍历非递归算法 #define maxsize 100 typedef enumL,R tagtype; typedef struct Bitree ptr;tagtype tag; stacknode

5、;|typedef struct stacknode Elemmaxsize;int top; SqStack; /后序遍历 void PostOrderUnrec(Bitree t) SqStack s;stacknode x;StackInit(s);p=t;do while (p!=null) / 遍历左子树x.ptr = p; x.tag = L; / 标记为左子树push(s,x);p=p-lchild;|while (!StackEmpty(s) p = x.ptr;visite(p-data); /tag 为 R ，表示右子树访问完毕，故访问根结点 if (!StackEmpty

6、(s)s.Elems.top.tag =R; /遍历右子树p=s.Elems.top.ptr-rchild; while (!StackEmpty(s); /PostOrderUnrec 3.后序遍历非递归算法 #define maxsize 100 typedef enumL,R tagtype; typedef struct Bitree ptr;tagtype tag; stacknode;|typedef struct stacknode Elemmaxsize;int top; SqStack; /后序遍历 void PostOrderUnrec(Bitree t) SqStack

7、s;stacknode x;StackInit(s);p=t;do while (p!=null) / 遍历左子树x.ptr = p; x.tag = L; / 标记为左子树push(s,x);p=p-lchild;|while (!StackEmpty(s) p = x.ptr;visite(p-data); /tag 为 R ，表示右子树访问完毕，故访问根结点 if (!StackEmpty(s)s.Elems.top.tag =R; /遍历右子树p=s.Elems.top.ptr-rchild; while (!StackEmpty(s); /PostOrderUnrec 2、线性表(1

8、) 性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双 向链表，双向循环链表。(2)单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除 算法等都是较为常见的考查方式。(3)单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的 各自好处。 3、栈与队列|你可以问一下自己是不是已经知道了以下几点：(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队 列，链队等。栈与队列存取数据(请注意包括：存和取两部分) 的特点。(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n! 阶乘 问题，fib

9、数列问题，hanoi 问题，背包问题，二叉树的递归和非递归遍历问题，图的深度 遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查 。(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求 考查此为题目的算法设计题不多。(4)循环队列中判队空、队满条件，循环队列中入队与出队( 循环队列在插入时也要判断 其是否已满，删除时要判断其是否已空) 算法。【循环队列的队空队满条件为了方便起见，约定：初始化建空队时，令front=rear=0,当队空时：front=rear ，当队满时：front=rear 亦成立，因此只凭等式 front=rear 无法

10、判断队空还是队满。有两种方法处理上述问题：(1)另设一个标志位以区别队列是空还是满。|(2)少用一个元素空间，约定以“队列头指针 front 在队尾指针 rear 的下一个位置上” 作为 队列“ 满”状态的标志。队空时： front=rear ，队满时： (rear+1)%maxsize=front】如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可 以不看书，并不是可以不作题哦。循环队列的主要操作：(1)创建循环队列(2)初始化循环队列(3)判断循环队列是否为空(4)判断循环队列是否为满(5)入队、出队/空出头尾之间的一个元素不用#include#include#de

11、fine MAXSIZE 100typedef struct|intelemMAXSIZE;intfront, rear;Quque; / 定义队头int initQue(Quque *q) /初始化(*q)-front=0;(*q)-rear=0;int isFull(Quque *q)if(q-front=(q-rear+1)%MAXSIZE)/判满(空出一个元素不用) 刘勉刚return 1;elsereturn 0;int insertQue(Quque *q,int elem)|if(isFull(*q)return -1;(*q)-elem(*q)-rear=elem;(*q)-r

12、ear=(*q)-rear+1)%MAXSIZE;/插入return0;int isEmpty(Quque *q)if(q-front=q-rear)/判空return 1;elsereturn 0;int deleteQue(Quque * q,int *pelem)if(isEmpty(*q)return 0;|*pelem=(*q)-elem(*q)-front;(*q)-front=(*q)-front +1)%MAXSIZE;return0; 4、串串一章需要攻破的主要堡垒有：1. 串的基本概念，串与线性表的关系( 串是其元素均为字符型数据的特殊线性表) ，空 串与空格串的区别，串相

13、等的条件;2. 串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串 长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。3. 顺序串与链串及块链串的区别和联系，实现方式。4. KMP 算法思想。KMP 中 next 数组以及 nextval 数组的求法。明确传统模式匹配算 法的不足，明确 next 数组需要改进。可能进行的考查方式是：求 next 和 nextval 数组值， 根据求得的 next 或 nextval 数组值给出运用 KMP 算法进行匹配的匹配过程。5、多维数组和广义表矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩

14、阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储 。|掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。6、树与二叉树树一章的知识点包括：二叉树的概念、性质和存储结构，二叉树遍历的三种算法(递归与非递归) ，在三种基 本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化 后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历 算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。(1) 二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树(左右子树无 序)的区别; 考查满二叉树和完

15、全二叉树的性质，普通二叉树的五个性质：A.第 i 层的最多结点数，B.深度为 k 的二叉树的最多结点数，C.n0=n2+1 的性质，D.n 个结点的完全二叉树的深度，E. 顺序存储二叉树时孩子结点与父结点之间的换算关系(root 从 1 开始，则左为：2*i ，右为：2*i+1)。二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示 方法。(2) 二叉树的三种遍历算法|这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的 算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据 是视其每个算法中对根结点数据的访问顺序而定。不仅要

16、熟练掌握三种遍历的递归算法， 理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很 多算法，可以直接根据三种递归算法改造而来( 比如：求叶子个数) ，所以，掌握了三种遍 历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如 有神了。(3) 可在三种遍历算法的基础上改造完成的其它二叉树算法：求叶子个数，求二叉树结点总数，求度为 1 或度为 2 的结点总数，复制二叉树，建立 二叉树，交换左右子树，查找值为 n 的某个指定结点，删除值为 n 的某个指定结点，诸如 此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题 就是

17、小菜一碟了。(4) 线索二叉树：线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式 上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危 险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握： 线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它 算法问题( 如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题) 。(5) 最优二叉树(哈夫曼树)：最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条 边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树

18、一节，直接考查算|法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其 最小权值之和，此类题目不难，属送分题。(6) 树与森林：二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为 2 以及其它特征，一个最 重要的特殊之处是在于：二叉树是有序的! 即：二叉树的左右孩子是不可交换的，如果交换 了就成了另外一棵二叉树。 树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算 法：先根与后根( 对于森林而言称作：先序与后序遍历) 。此二者的先根与后根遍历与二叉 树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉 树的中序遍历。二叉树、树与森林之所

19、以能有以上的对应关系，全拜二叉链表所赐。二叉 树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟(称孩子兄弟链表) ， 而森林也是利用二叉链表存储孩子及兄弟。 7、图1. 图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子 图，路径长度，回路，( 强)连通图，(强) 连通分量等概念。2. 图的几种存储形式：邻接矩阵，( 逆) 邻接表，十字链表及邻接多重表。在考查时， 有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另 一种存储形式。3. 考查图的两种遍历算法：深度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法

20、对图一章的重要性等同 于“先序、中序、后序遍历” 对于二叉树一章的重要性。在考查时，图一章的算法设计题常|常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点 间是否存在长为 K 的简单路径问题”，就分别用到了广度遍历和深度遍历算法。4. 生成树、最小生成树的概念以及最小生成树的构造：PRIM 算法和 KRUSKAL 算法 。考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出 其构造过程及最终生成的最小生成树。5. 拓扑排序问题：拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换 句话说，一种是“ 从前向后” 的排序

21、，一种是“ 从后向前” 排。当然，后一种排序出来的结果 是“逆拓扑有序” 的。6. 关键路径问题：这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径;二是最早时间是什么意思、如何求;三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后” 的方法求的，而最晚时间是通过“从后向前”的 方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行 。|在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求 最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的 最早时间全部置为 0。关键路径问题是工程

22、进度控制的重要方法，具有很强的实用性。7. 最短路径问题：与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的 理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径(单源最短路径); 二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型 的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用 DIJSKTRA 算法，解决第 二个问题用 FLOYD 算法，注意区分。 8、查找(search)先弄清楚以下几个概念：关键字、主关键字、次关键字的含义;静态查找与动态查找的 含义及区别; 平均查找长度 ASL 的概念及在各种查找算法中的计算

23、方法和计算结果，特别 是一些典型结构的 ASL 值，应该记住。一般将 search 分为三类：在顺序表上的查找; 在树表上的查找; 在哈希表上的查找。(1) 线性表上的查找：主要分为三种线性结构：顺序表传统查找方法：逐个比较;有序顺序表二分查找法(注意适用条件以及其递归实现方法);索引顺序表对索引结构，采用索引查找算法。注意这三种表下的 ASL 值以及三种 算法的实现。|(2) 树表上的查找：树表主要分为以下几种：二叉排序树( 即二叉查找树)，平衡二叉查找树(AVL 树) ，B 树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考 B 树的。由于二叉排序树与 平衡二叉树是一种特殊的二叉树。二

24、叉排序树，简言之，就是“左小右大” ，它的中序遍历结果是一个递增的有序序列。 平衡二叉排序树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡排序二 叉树对左右子树的深度有了限定：深度之差的绝对值不得大于 1。对于二叉排序树，“判断 某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉 树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法， 调整的一个参照是：调整前后的中序遍历结果相同。B 树是二叉排序树的进一步改进，也可以把 B 树理解为三叉、四叉.排序树。除 B 树 的查找算法外，应该特别注意一下 B 树的插入和删除算法，因为这两

25、种算法涉及到 B 树结 点的分裂和合并，是一个难点。 键树(keywordtree)，又称数字搜索树(digitalsearch tree)或 字符树。trie 树也可说等同于键树或属于键树的一种。键树特别适用于查找英文单词的场 合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程 。(3) 基于哈希表的查找算法：哈希译自“hash”一词，意为“散列” 或“ 杂凑”。哈希表查找的基本思想是：根据当前待查 找数据的特征，以记录关键字为自变量，设计一个 function，该函数对关键字进行转换后 ，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法

26、的 选择及冲突处理过程的描述。 9、内部排序|考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度) 能否 了如指掌。排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。(1)插入排序中又可分为：直接插入、折半插入、2 路插入(?)、希尔排序。这几种插入 排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是 依次寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范围“由小 到大” 的增量来实现排序效率提高的目的。(2)交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排 序的思想，一语以敝之：用中间数将待排

27、数据组一分为二。(3)选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算 法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数;树选择，是通过“ 锦标赛”类似的思想，让两数相比，不断淘汰较大( 小)者，最终选出 最小(大) 数;而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将 最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。(4)归并排序，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上 的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是 2 路归并。算

28、法思想 比较简单，有一点，要铭记在心：归并排序是稳定排序。|(5)基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比 较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的 排序(扑克牌排序)，链式排序(整数排序) 。基数排序的核心思想也是利用“基数空间”这个概 念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关 键字比较的，这样得出的最终序列就是一个有序序列。本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的。/稳定性分析/排序算法的稳定性，通俗地讲就是能保证排序前 2 个相等的数其在序列的前后位置顺

29、序和排序后它们两个的前后位置顺序相同。稳定性的好处：若排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键 上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排 序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果 排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没 有证实)。分析一下常见的排序算法的稳定性，每个都给出简单的理由。(1) 冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较 ，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他 们俩交换

30、一下的; 如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻 起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳 定排序算法。|(2) 选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余 元素里面给第二个元素选择第二小的，依次类推，直到第 n-1 个元素，第 n 个元素不用选 择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小 ，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了 。比较拗口，举个例子，序列 5 8 5 2 9，我们知道第一遍选择第 1 个元素 5 会

31、和 2 交换 ，那么原序列中 2 个 5 的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算 法。(3) 插入排序插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这 个有序的小序列只有 1 个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是 想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一 直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想 插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出 去的顺序就是排好序后的顺序，所以插入排序是稳定的。(4) 快速排序快速排序有两

32、个方向，左边的 i 下标一直往右走，当 ai acenter_index。如果 i 和 j 都走不动了，i j。交换 aj 和 acenter_index ，完成一趟快速排序。在中枢元素和 aj 交换的时候 ，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元|素 5 和 3( 第 5 个元素，下标从 1 开始计) 交换就会把元素 3 的稳定性打乱，所以快速排序是 一个不稳定的排序算法，不稳定发生在中枢元素和 aj 交换的时刻。(5) 归并排序归并排序是把序列递归地分成短序列，递归出口是短序列只有 1 个元素(认为直接有序) 或 者 2 个序列(1

33、 次比较和交换), 然后把各个有序的段序列合并成一个有序的长序列，不断合 并直到原序列全部排好序。可以发现，在 1 个或 2 个元素时，1 个元素不会交换，2 个元素 如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程 中，稳定是是否受到破坏? 没有，合并过程中我们可以保证如果两个当前元素相等时，我们 把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序 也是稳定的排序算法。(6) 基数排序基数排序是按照低位先排序，然后收集;再按照高位排序，然后再收集; 依次类推，直 到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级

34、排序， 最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分 别排序，分别收集，所以其是稳定的排序算法。(7) 希尔排序(shell)希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最 大，所以插入排序的元素个数很少，速度很快;当元素基本有序了，步长很小，插入排序对 于有序的序列效率很高。所以，希尔排序的时间复杂度会比 o(n2)好一些。由于多次插入 排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入 排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以 shell 排序是不稳定的。|(8)

35、 堆排序我们知道堆的结构是节点 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 个相同的元素之间的稳定性就被破坏了。所以 ，堆排序不是稳定的

36、排序算法。 冒泡排序 插入排序 二路插入排序 希尔排序 快速排序 选择排序 归并排序 堆排序算法的 C/C+实现#include using namespace std;/交换两个数的值void swap(int tmp=a;a=b;b=tmp;|/屏幕输出数组void display(int array,int len)cout for (int i = 0 ;i 重者在下为止。时间复杂度 o(n2)空间复杂度 o(1)比较次数 n(n+1)/2*/void bubble_sort(int array,int len)for (int i = len-1 ;i = 0;i- )|for(in

37、t j = 0;j arrayj+1)swap(arrayj,arrayj+1);/* 直接插入排序算法思想：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只 包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复 n-1 次可完成排序过程。时间复杂度 o(n2)空间复杂度 o(1)比较次数 n(n+1)/2*/void insert_sort(int array,int len)|int tmp,i,j;for(i = 1;i = 0;j-)/往后移if (arrayj tmp)arra

38、yj+1 =arrayj;elsearrayj+1 = tmp;break;|if(j = -1)arrayj+1 = tmp;/* 2-路插入排序算法思想：增加一个辅助空间 d,把 r1赋值给 d1，并将 d1看成是排好序后处于中 间位置的记录。然后从 r2开始依次插入到 d1之前或之后的有序序列中。时间复杂度 o(n2)空间复杂度 o(1)比较次数 n(n+1)/2*/void bi_insert_sort(int array,int len)|int* arr_d = (int*)malloc(sizeof(int) * len);arr_d0 = array0;int head = 0

39、,tail = 0;for (int i = 1;i arr_d0)int j;for ( j= tail;j0;j-)if (arrayi arr_dj+1 =arr_dj;elsebreak;arr_dj+1 = arrayi;|tail += 1;elseif (head =0)arr_dlen-1 = arrayi;head =len-1;elseint j;for (j = head;j arr_dj)arr_dj-1 =arr_dj;else|break;arr_dj-1 = arrayi;head -= 1;for (int i = 0;i = len) pos -= len;arrayi = arr_dpos;free(arr_d);/* 希尔排序|算法思想：先将整个待排序记录分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序时间复杂度 o(n2)空间复杂度 o(1)比较次数 ?*/void shell_insert(int array,int d,int len)int tmp,j;for (int i = d;i = 0