1、二叉树三种遍历的非递归算法（背诵版）
本贴给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。
1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
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) &&s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
4.层次遍历算法
// 二叉树的数据结构
structBinaryTree
{
int value; // 不写模板了，暂时用整形代替节点的数据类型
BinaryTree *left;
BinaryTree *right;
};
BinaryTree*root; // 已知二叉树的根节点
//层次遍历
voidLevel( const BinaryTree *root )
{
Queue *buf = new Queue(); // 定义一个空队列，假设此队列的节点数据类型也是整形的
BinaryTree t; // 一个临时变量
buf.push_back(root); //令根节点入队
while( buf.empty == false ) // 当队列不为空
{
p = buf.front(); // 取出队列的第一个元素
cout<
if( p->left != NULL ) // 若左子树不空，则令其入队
{
q.push( p->left );
}
if( p->right != NULL ) // 若右子树不空，则令其入队
{
q.push( p->right );
}
buf.pop(); // 遍历过的节点出队
}
cout< } 2、线性表 （1）性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。 （2）单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。 （3）单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。 3、栈与队列 你可以问一下自己是不是已经知道了以下几点： (1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。 (2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。 (3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。 (4)循环队列中判队空、队满条件，循环队列中入队与出队（循环队列在插入时也要判断其是否已满，删除时要判断其是否已空）算法。 【循环队列的队空队满条件 为了方便起见，约定：初始化建空队时，令 front=rear=0, 当队空时：front=rear， 当队满时：front=rear 亦成立， 因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题： （1）另设一个标志位以区别队列是空还是满。 （2）少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。 队空时：front=rear， 队满时：(rear+1)%maxsize=front】 如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。 //////////////////////////////////////////////////////////////////////////////////////////////// 循环队列的主要操作： (1)创建循环队列 (2)初始化循环队列 (3)判断循环队列是否为空 (4)判断循环队列是否为满 (5)入队、出队 //空出头尾之间的一个元素不用 #include #include #define MAXSIZE 100 typedef struct { intelem[MAXSIZE]; 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; else return 0; } int insertQue(Quque **q,int elem) { if(isFull(*q))return -1; (*q)->elem[(*q)->rear]=elem; (*q)->rear=((*q)->rear+1)%MAXSIZE;//插入 return0; } int isEmpty(Quque *q) { if(q->front==q->rear)//判空 return 1; else return 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. 串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件； 2. 串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。 3. 顺序串与链串及块链串的区别和联系，实现方式。 4. KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。 5、多维数组和广义表 矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。 熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。 掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。 6、树与二叉树 树一章的知识点包括： 二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。 (1) 二叉树的概念、性质和存储结构 考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树(左右子树无序)的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质： A.第i层的最多结点数， B.深度为k的二叉树的最多结点数， C.n0=n2+1的性质， D.n个结点的完全二叉树的深度， E. 顺序存储二叉树时孩子结点与父结点之间的换算关系（root从1开始，则左为：2*i，右为：2*i+1）。 二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。 (2) 二叉树的三种遍历算法 这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。 (3) 可在三种遍历算法的基础上改造完成的其它二叉树算法： 求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。 (4) 线索二叉树： 线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形 式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。 (5) 最优二叉树（哈夫曼树）： 最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。 (6) 树与森林： 二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树。树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。 7、图 1. 图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。 2. 图的几种存储形式：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。 3. 考查图的两种遍历算法：深度遍历和广度遍历 深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。 4. 生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。 考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。 5. 拓扑排序问题： 拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。 6. 关键路径问题： 这个问题是图一章的难点问题。理解关键路径的关键有三个方面： 一是何谓关键路径； 二是最早时间是什么意思、如何求； 三是最晚时间是什么意思、如何求。 简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。 在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。 7. 最短路径问题： 与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径（单源最短路径）；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法，注意区分。 8、查找（search） 先弄清楚以下几个概念：关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。 一般将search分为三类：在顺序表上的查找；在树表上的查找；在哈希表上的查找。 （1）线性表上的查找： 主要分为三种线性结构： 顺序表——传统查找方法：逐个比较； 有序顺序表——二分查找法（注意适用条件以及其递归实现方法）； 索引顺序表——对索引结构，采用索引查找算法。注意这三种表下的ASL值以及三种算法的实现。 （2）树表上的查找： 树表主要分为以下几种：二叉排序树（即二叉查找树），平衡二叉查找树（AVL树），B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树。 二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉排序树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡排序二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。 B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B 树的查找算法外，应该特别注意一下B树的插入和删除算法，因为这两种算法涉及到B树结点的分裂和合并，是一个难点。键树（keywordtree），又称数字搜索树（digitalsearch tree） 或字符树。trie树也可说等同于键树或属于键树的一种。键树特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。 （3）基于哈希表的查找算法： 哈希译自“hash”一词，意为“散列”或“杂凑”。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。 9、内部排序 考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。 排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。 （1）插入排序中又可分为：直接插入、折半插入、2路插入（？）、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。 （2）交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。 （3）选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。 简单选择，是通过简单的数组遍历方案确定最小数； 树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数； 而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。 （4）归并排序，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。 （5）基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。 本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的。 //////////////////////////////////////////////稳定性分析//////////////////////////////////////////////// 排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。 稳定性的好处：若排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。 分析一下常见的排序算法的稳定性，每个都给出简单的理由。 (1) 冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 (2) 选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 (3) 插入排序 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 (4) 快速排序 快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j]> a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。 (5) 归并排序 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素 如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。 (6) 基数排序 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。 (7) 希尔排序(shell) 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 (8) 堆排序 我们知道堆的结构是节点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个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。 ////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////// 冒泡排序插入排序二路插入排序希尔排序快速排序选择排序归并排序堆排序算法的C/C++实现////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// #include using namespace std; //交换两个数的值 void swap(int &a,int &b) { int tmp; tmp=a; a=b; b=tmp; } //屏幕输出数组 void display(int array[],int len) { cout<<"the resultis:"< for (int i = 0 ;i < len;i++ ) { cout< } cout< } /* 冒泡排序 算法思想：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。 根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的 轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上， 重者在下为止。 时间复杂度o(n^2) 空间复杂度o(1) 比较次数n(n+1)/2 */ void bubble_sort(int array[],int len) { for (int i = len-1 ;i >= 0;i-- ) { for(int j = 0;j < i;j++) if(array[j] > array[j+1]) swap(array[j],array[j+1]); } } /* 直接插入排序 算法思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元 素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它 插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。时间复杂度o(n^2) 空间复杂度o(1) 比较次数n(n+1)/2 */ void insert_sort(int array[],int len) { int tmp,i,j; for(i = 1;i < len;i++) { if (array[i] < array[i-1]) { tmp = array[i]; array[i] = array[i-1]; //插入到相应位置 for (j = i-2;j >= 0;j--) { //往后移 if (array[j] > tmp) array[j+1] =array[j]; else { array[j+1] = tmp; break; } } if(j == -1) array[j+1] = tmp; } } } /* 2-路插入排序 算法思想：增加一个辅助空间d,把r[1]赋值给d[1]，并将d[1]看成是排好序后处于中间位置的记录。然后从r[2]开始依次插入到d[1]之前或之后的有序序列中。 时间复杂度o(n^2) 空间复杂度o(1) 比较次数n(n+1)/2 */ void bi_insert_sort(int array[],int len) { int* arr_d = (int*)malloc(sizeof(int) * len); arr_d[0] = array[0]; int head = 0,tail = 0; for (int i = 1;i < len; i++ ) { if (array[i] > arr_d[0]) { int j; for ( j= tail;j>0;j--) { if (array[i] arr_d[j+1] =arr_d[j]; else break; } arr_d[j+1] = array[i]; tail += 1; } else { if (head ==0) { arr_d[len-1] = array[i]; head =len-1; } else { int j; for (j = head;j <=len-1;j++) { if (array[i] >arr_d[j]) arr_d[j-1] =arr_d[j]; else break; } arr_d[j-1] = array[i]; head -= 1; } } } for (int i = 0;i < len; i++) { int pos = (i + head ); if(pos >= len) pos -= len; array[i] = arr_d[pos]; } free(arr_d); } /* 希尔排序 算法思想：先将整个待排序记录分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一 次直接插入排序 时间复杂度o(n^2) 空间复杂度o(1) 比较次数? */ void shell_insert(int array[],int d,int len) { int tmp,j; for (int i = d;i < len;i++) { if(array[i] < array[i-d]) { tmp = array[i]; j = i - d; do { array[j+d] = array[j]; j = j - d; } while (j >= 0 &&tmp < array[j]); array[j+d] = tmp; } } } void shell_sort(int array[],int len) { int inc = len; do { inc = inc/2; shell_insert(array,inc,len); } while (inc > 1); } /* 快速排序 算法思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。 递归地解这些子问题，然后将这些子问题的解组合成为原问题的解。 时间复杂度o(nlogn) 空间复杂度o(logn) 比较次数? */ void quick_sort(int array[],int low,int high) { if (low < high) { int pivotloc =partition(array,low,high); quick_sort(array,low,pivotloc-1); quick_sort(array,pivotloc+1,high); } } int partition(int array[],int low,int high) { int pivotkey = array[low]; while (low < high) { while(low < high &&array[high] >= pivotkey) --high; swap(array[low],array[high]); while(low < high &&array[low] <= pivotkey) ++low; swap(array[low],array[high]); } array[low] = pivotkey; return low; } /* 直接选择排序 算法思想：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中的第i个记录 时间复杂度o(n^2) 空间复杂度o(1) ? 比较次数n(n+1)/2 */ int SelectMinKey(int array[],int iPos,int len) { int ret = 0; for (int i = iPos; i < len; i++) { if (array[ret] > array[i]) { ret = i; } } return ret; } void select_sort(int array[],int len) { for (int i = 0; i < len; i++) { int j =SelectMinKey(array,i,len); if (i != j) { swap(array[i],array[j]); } } } /* 归并排序 算法思想：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。 时间复杂度o(nlogn) 空间复杂度o(n) 比较次数? */ void merge(int array[],int i,int m, int n)
相关主题
文本预览