描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302500988丛书名: 高等学校数据结构课程系列教材
全书既注重原理又注重实践，配有大量图表、练习题、上机实验题和在线编程题，内容丰富，概念讲解清楚，表达严谨，逻辑性强，语言精练，可读性好。
本书既便于教师课堂讲授，又便于自学者阅读，适合作为高等院校“算法设计与分析”课程的教材，也可供ACM和各类程序设计竞赛者参考。
目录
第1章概论/
1.1算法的概念/
1.1.1什么是算法/
1.1.2算法描述/
1.1.3算法和数据结构/
1.1.4算法设计的基本步骤/
1.2算法分析/
1.2.1算法时间复杂度分析/
1.2.2算法空间复杂度分析/
1.3算法设计工具——STL/
1.3.1STL概述/
1.3.2常用的STL容器/
1.3.3STL在算法设计中的应用/
1.4练习题/
1.5上机实验题/
1.6在线编程题/
第2章递归算法设计技术/
2.1什么是递归/
2.1.1递归的定义/
2.1.2何时使用递归/
2.1.3递归模型/
2.1.4递归算法的执行过程/
2.2递归算法设计/
2.2.1递归与数学归纳法/
2.2.2递归算法设计的一般步骤/
2.2.3递归数据结构及其递归算法设计/
2.2.4基于归纳思想的递归算法设计/
2.3递归算法设计示例/
2.3.1简单选择排序和冒泡排序/
2.3.2求解n皇后问题/
2.4*递归算法转化为非递归算法/
2.4.1用循环结构替代递归过程/
2.4.2用栈消除递归过程/
2.5递推式的计算/
2.5.1用特征方程求解递归方程/
2.5.2用递归树求解递归方程/
2.5.3用主方法求解递归方程/
2.6练习题/
2.7上机实验题/
2.8在线编程题/
第3章分治法/
3.1分治法概述/
3.1.1分治法的设计思想/
3.1.2分治法的求解过程/
3.2求解排序问题/
3.2.1快速排序/
3.2.2归并排序/
3.3求解查找问题/
3.3.1查找最大和次大元素/
3.3.2折半查找/
3.3.3寻找一个序列中第k小的元素/
3.3.4寻找两个等长有序序列的中位数/
3.4求解组合问题/
3.4.1求解最大连续子序列和问题/
3.4.2求解棋盘覆盖问题/
3.4.3求解循环日程安排问题/
3.5求解大整数乘法和矩阵乘法问题/
3.5.1求解大整数乘法问题/
3.5.2求解矩阵乘法问题/
3.6并行计算简介/
3.6.1并行计算概述/
3.6.2并行计算模型/
3.6.3快速排序的并行算法/
3.7练习题/
3.8上机实验题/
3.9在线编程题/
第4章蛮力法/
4.1蛮力法概述/
4.2蛮力法的基本应用/
4.2.1采用直接穷举思路的一般格式/
4.2.2简单选择排序和冒泡排序/
4.2.3字符串匹配/
4.2.4求解最大连续子序列和问题/
4.2.5求解幂集问题/
4.2.6求解简单0/1背包问题/
4.2.7求解全排列问题/
4.2.8求解任务分配问题/
4.3递归在蛮力法中的应用/
4.3.1用递归方法求解幂集问题/
4.3.2用递归方法求解全排列问题/
4.3.3用递归方法求解组合问题/
4.4图的深度优先和广度优先遍历/
4.4.1图的存储结构/
4.4.2深度优先遍历/
4.4.3广度优先遍历/
4.4.4求解迷宫问题/
4.5练习题/
4.6上机实验题/
4.7在线编程题/
第5章回溯法/
5.1回溯法概述/
5.1.1问题的解空间/
5.1.2什么是回溯法/
5.1.3回溯法的算法框架及其应用/
5.1.4回溯法与深度优先遍历的异同/
5.1.5回溯法的时间分析/
5.2求解0/1背包问题/
5.3求解装载问题/
5.3.1求解简单装载问题/
5.3.2求解复杂装载问题/
5.4求解子集和问题/
5.4.1求子集和问题的解/
5.4.2判断子集和问题是否存在解/
5.5求解n皇后问题/
5.6求解图的m着色问题/
5.7求解任务分配问题/
5.8求解活动安排问题/
5.9求解流水作业调度问题/
5.10练习题/
5.11上机实验题/
5.12在线编程题/
第6章分枝限界法/
6.1分枝限界法概述/
6.1.1什么是分枝限界法/
6.1.2分枝限界法的设计思想/
6.1.3分枝限界法的时间性能/
6.2求解0/1背包问题/
6.2.1采用队列式分枝限界法求解/
6.2.2采用优先队列式分枝限界法求解/
6.3求解图的单源最短路径/
6.3.1采用队列式分枝限界法求解/
6.3.2采用优先队列式分枝限界法求解/
6.4求解任务分配问题/
6.5求解流水作业调度问题/
6.6练习题/
6.7上机实验题/
6.8在线编程题/
第7章贪心法/
7.1贪心法概述/
7.1.1什么是贪心法/
7.1.2用贪心法求解的问题应具有的性质/
7.1.3贪心法的一般求解过程/
7.2求解活动安排问题/
7.3求解背包问题/
7.4求解最优装载问题/
7.5求解田忌赛马问题/
7.6求解多机调度问题/
7.7哈夫曼编码/
7.8求解流水作业调度问题/
7.9练习题/
7.10上机实验题/
7.11在线编程题/
第8章动态规划/
8.1动态规划概述/
8.1.1从求解斐波那契数列看动态规划法/
8.1.2动态规划的原理/
8.1.3动态规划求解的基本步骤/
8.1.4动态规划与其他方法的比较/
8.2求解整数拆分问题/
8.3求解最大连续子序列和问题/
8.4求解三角形最小路径问题/
8.5求解最长公共子序列问题/
8.6求解最长递增子序列问题/
8.7求解编辑距离问题/
8.8求解0/1背包问题/
8.9求解完全背包问题/
8.10求解资源分配问题/
8.11求解会议安排问题/
8.12滚动数组/
8.12.1什么是滚动数组/
8.12.2用滚动数组求解0/1背包问题/
8.13练习题/
8.14上机实验题/
8.15在线编程题/
第9章图算法设计/
9.1求图的最小生成树/
9.1.1最小生成树的概念/
9.1.2用普里姆算法构造最小生成树/
9.1.3克鲁斯卡尔算法/
9.2求图的最短路径/
9.2.1狄克斯特拉算法/
9.2.2贝尔曼福特算法/
9.2.3SPFA算法/
9.2.4弗洛伊德算法/
9.3求解旅行商问题/
9.3.1旅行商问题描述/
9.3.2采用蛮力法求解TSP问题/
9.3.3采用动态规划求解TSP问题/
9.3.4采用回溯法求解TSP问题/
9.3.5采用分枝限界法求解TSP问题/
9.3.6采用贪心法求解TSP问题/
9.4网络流/
9.4.1相关概念/
9.4.2求最大流/
9.4.3割集与割量/
9.4.4求最小费用最大流/
9.5练习题/
9.6上机实验题/
9.7在线编程题/
第10章计算几何/
10.1向量运算/
10.1.1向量的基本运算/
10.1.2判断一个点是否在一个矩形内/
10.1.3判断一个点是否在一条线段上/
10.1.4判断两条线段是否平行/
10.1.5判断两条线段是否相交/
10.1.6判断一个点是否在多边形内/
10.1.7求3个点构成的三角形的面积/
10.1.8求一个多边形的面积/
10.2求解凸包问题/
10.2.1礼品包裹算法/
10.2.2Graham扫描算法/
10.3求解最近点对问题/
10.3.1用蛮力法求最近点对/
10.3.2用分治法求最近点对/
10.4求解最远点对问题/
10.4.1用蛮力法求最远点对/
10.4.2用旋转卡壳法求最远点对/
10.5练习题/
10.6上机实验题/
10.7在线编程题/
第11章计算复杂性理论简介/
11.1计算模型/
11.1.1求解问题的分类/
11.1.2图灵机模型/
11.2P类和NP类问题/
11.3NPC问题/
11.4练习题/
第12章概率算法和近似算法/
12.1概率算法/
12.1.1什么是概率算法/
12.1.2蒙特卡罗类型概率算法/
12.1.3拉斯维加斯类型概率算法/
12.1.4舍伍德类型概率算法/
12.2近似算法/
12.2.1什么是近似算法/
12.2.2求解旅行商问题的近似算法/
12.3练习题/
12.4上机实验题/
12.5在线编程题/
附录A书中部分算法清单/
参考文献/
前言
算法在计算科学中扮演着重要角色。算法设计是计算机科学与技术专业的必修课，其目标是培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本技巧和方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法策略解决一些较综合的问题。在学习本书之前，学生已经学习了基本的数据结构知识，能熟练运用一门或多门编程语言，并具备了一定的编程经验。如何利用已学过的知识针对不同的实际问题设计出有效的算法，是本书所要达到的目的。本书的特点是“问题模型化，求解算法化，设计最优化”，在掌握必要的算法设计技术和编程技巧的基础上，能够在实际工作中根据具体问题设计和优化算法。本书是针对这一特点并结合课程组全体教师多年的教学经验编写的。1. 本书内容全书由12章构成，各章的内容如下。第1章概论： 介绍算法的概念、算法分析方法和STL在算法设计中的应用。第2章递归算法设计技术： 介绍递归的概念、递归算法设计方法和相关示例、递归算法到非递归算法的转化以及递推式的计算。第3章分治法： 介绍分治法的策略和求解过程，讨论采用分治法求解排序问题、查找问题、最大连续子序列和问题、大整数乘法问题及矩阵乘法问题的典型算法，并简要介绍了并行计算的概念。第4章蛮力法： 介绍蛮力法的特点、蛮力法的基本应用示例、递归在蛮力法中的应用以及图的深度优先和广度优先遍历算法。第5章回溯法： 介绍解空间概念和回溯法算法框架，讨论采用回溯法求解0/1背包问题、装载问题、子集和问题、n皇后问题、图的m着色问题、任务分配问题、活动安排问题和流水作业调度问题的典型算法。第6章分枝限界法： 介绍分枝限界法的特点和算法框架、队列式分枝限界法和优先队列式分枝限界法，讨论采用分枝限界法求解0/1背包问题、图的单源最短路径、任务分配问题和流水作业调度问题的典型算法。第7章贪心法： 介绍贪心法的策略、求解过程和贪心法求解问题应具有的性质，讨论采用贪心法求解活动安排问题、背包问题、最优装载问题、田忌赛马问题、多机调度问题、哈夫曼编码和流水作业调度问题的典型算法。第8章动态规划： 介绍动态规划的原理和求解步骤，讨论采用动态规划法求解整数拆分问题、最大连续子序列和问题、三角形最小路径问题、最长公共子序列问题、最长递增子序列问题、编辑距离问题、0/1背包问题、完全背包问题、资源分配问题、会议安排问题和滚动数组的典型算法。第9章图算法设计： 讨论构造图最小生成树的两种算法(Prim和Kruskal算法，并查集的应用)、求图的最短路径的4种算法(Dijkstra、BellmanFord、SPFA和Floyd)，并采用5种算法策略求解旅行商问题(TSP问题)，最后介绍网络流的相关概念以及求最大流和最小费用最大流的算法。第10章计算几何： 介绍计算几何中常用的矢量运算以及求解凸包问题、最近点对问题和最远点对问题的典型算法。第11章计算复杂性理论简介： 介绍图灵机计算模型、P类和NP类问题以及NPC问题。第12章概率算法和近似算法： 介绍这两类算法的特点和基本的算法设计方法。书中带“*”符号的章节作为选学内容。2. 本书特色本书具有如下鲜明特色。(1) 由浅入深，循序渐进： 每种算法策略从设计思想、算法框架入手，由易到难地讲解经典问题的求解过程，使读者既能学到求解问题的方法，又能通过对算法策略的反复应用掌握其核心原理，以收到融会贯通之效。(2) 示例丰富，重视启发： 书中列举大量的具有典型性的求解问题，深入剖析采用相关算法策略求解的思路，展示算法设计的清晰过程，并举一反三，激发学生学习算法设计的兴趣。(3) 注重求解问题的多维性： 同一个问题采用多种算法策略实现，如0/1背包问题采用回溯法、分枝限界法和动态规划求解，旅行商问题采用5种算法策略求解。通过不同算法策略的比较，使学生更容易体会到每一种算法策略的设计特点和各自的优/缺点，以提高算法设计的效率。(4) 强调实验和动手能力的培养： 算法讲解不仅包含思路描述，而且以C/C 完整程序的形式呈现，同时给出了大量的上机实验题和在线编程题，大部分是近几年国内外的著名IT企业面试笔试题(谷歌、微软、阿里巴巴、腾讯、网易等)和ACM竞赛题。通过这些题目的训练，不仅可以提高学生的编程能力，而且可以帮助其直面求职市场。（5） 本书配套有《算法设计与分析（第2版）学习与实验指导》（李春葆，清华大学出版社，2018），涵盖所有练习题、上机实验题和在线编程题的参考答案。（6） 本书配套有绝大部分知识点的教学视频，视频采用微课碎片化形式组织（含100多个小视频，累计超过20小时），读者通过扫描二维码即可观看相关视频讲解。3. 教学资源本书提供的教学资源包括完整的教学PPT和书中全部源程序代码(在VC 6．0中调试通过)，用户可以扫描封底课件二维码免费下载。4. 感谢本书的编写得到湖北省教育厅和武汉大学教学研究项目《计算机科学与技术专业课程体系改革》的大力帮助，清华大学出版社的魏江江主任全力支持本书的编写工作，王冰飞老师给予精心的编辑工作。本书在编写过程中参考了很多同行的教材和网络博客，特别是“牛客网”中众多的企业面试、笔试题和丰富资源给予编者良好的启发，河南工程学院张天伍老师和使用本教材第1版的多位老师指正多处问题和错误，在此一并表示衷心感谢。本书是课程组全体教师多年教学经验的总结和体现，尽管编者不遗余力，但由于水平所限，难免存在不足之处，敬请教师和同学们批评指正，在此表示衷心感谢。编者
2018年5月
分治法是使用最广泛的算法设计方法之一。其基本策略是采用递归思想把大问题分解成一些小问题，然后由小问题的解方便地构造出大问题的解。本章介绍分治法求解问题的一般方法，并给出一些用分治法求解的经典示例。3.1分治法概述3.1.1分治法的设计思想对于一个规模为n的问题，若该问题可以容易地解决(例如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解，这种算法设计策略叫分治法。如果原问题可分割成k(1
divideandconquer(P)
{if |P|≤n0 return adhoc(P);
将P分解为较小的子问题 P1、P2、…、Pk;
for(i=1;i<=k;i )//循环处理k次
yi=divideandconquer(Pi); //递归解决Pi
return merge(y1,y2,…,yk); //合并子问题
}
其中，|P|表示问题P的规模； n0为一阈值，表示当问题P的规模不超过n0时(即P问题规模足够小时)已容易直接解出，不必再继续分解。adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。算法merge(y1，y2，…，yk)是该分治法中的合并子算法，用于将P的子问题P1、P2、…、Pk的相应解y1、y2、…、yk合并为P的解。根据分治法的分解原则，原问题应该分解为多少个子问题才较适合？各个子问题的规模应该怎样才为适当？这些问题很难给予肯定的回答。但人们从大量
图3.1二分法的基本策略
的实践中发现，在用分治法设计算法时最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。当k=1时称为减治法。许多问题可以取k=2，称为二分法，如图3.1所示，这种使子问题规模大致相等的做法出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题的合并方法比较复杂，或者是有多种合并方案； 或者是合并方案不明显。究竟应该怎样合并没有统一的模式，需要具体问题具体分析。尽管许多分治法算法都是采用递归实现的，但要注意分治法和递归是有区别的，分治法是一种求解问题的策略，而递归是一种实现求解算法的技术。分治法算法也可以采用非递归方法实现。就像二分查找，作为一种典型的分治法算法，既可以采用递归实现，也可以采用非递归实现。3.2求解排序问题对于给定的含有n个元素的数组a，对其按元素值递增排序。快速排序和归并排序是典型的采用分治法进行排序的方法。3.2.1快速排序
快速排序的基本思想是在待排序的n个元素中任取一个元素(通常取第一个元素)作为基准，把该元素放入最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称为划分，如图3.2所示。然后对两个子序列分别重复上述过程，直到每个子序列内只有一个元素或空为止。
图3.2快速排序的一趟排序过程
这是一种二分法思想，每次将整个无序序列一分为二，归位一个元素，对两个子序列采用同样的方式进行排序，直到子序列的长度为1或0为止。快速排序的分治策略如下。(1) 分解： 将原序列a［s..t］分解成两个子序列a［s..i-1］和a［i 1..t］，其中i为划分的基准位置，即将整个问题分解为两个子问题。(2) 求解子问题： 若子序列的长度为0或1，则它是有序的，直接返回； 否则递归地求解各个子问题。(3) 合并： 由于整个序列存放在数组a中，排序过程是就地进行的，合并步骤不需要执行任何操作。 例如，对于(2，5，1，7，10，6，9，4，3，8)序列，其快速排序过程如图3.3所示，图中虚线表示一次划分，虚线旁的数字表示执行次序，圆圈表示归位的基准。
图3.3(2，5，1，7，10，6，9，4，3，8)序列的快速排序过程
实现快速排序的完整程序如下：
#include
void disp(int a［］,int n)//输出a中的所有元素
{int i;
for (i=0;iprintf(“%d “,a［i］);
printf(“＼n”);
}
int Partition(int a［］,int s,int t) //划分算法
{int i=s,j=t;
int tmp=a［s］; //用序列的第1个记录作为基准
while (i!=j) //从序列两端交替向中间扫描,直到i=j为止
{while (j>i && a［j］>=tmp)
j–; //从右向左扫描,找第1个关键字小于tmp的a［j］
a［i］=a［j］; //将a［j］前移到a［i］的位置
while (ii ; //从左向右扫描,找第1个关键字大于tmp的a［i］
a［j］=a［i］; //将a［i］后移到a［j］的位置
}
a［i］=tmp;
return i;
}
void QuickSort(int a［］,int s,int t) //对a［s..t］元素序列进行递增排序
{if (s //序列内至少存在两个元素的情况
{int i=Partition(a,s,t);
QuickSort(a,s,i-1); //对左子序列递归排序
QuickSort(a,i 1,t); //对右子序列递归排序
}
}
void main()
{int n=10;
int a［］={2,5,1,7,10,6,9,4,3,8};
printf(“排序前:”); disp(a,n);
QuickSort(a,0,n-1);
printf(“排序后:”); disp(a,n);
}
【算法分析】快速排序的时间主要耗费在划分操作上，对长度为n的区间进行划分，共需n-1次关键字的比较，时间复杂度为O(n)。对n个元素进行快速排序的过程构成一棵递归树，在这样的递归树中，每一层最多对n个元素进行划分，所花的时间为O(n)。当初始排序数据正序或反序时，递归树高度为n，快速排序呈现最坏情况，即最坏情况下的时间复杂度为O(n2)； 当初始排序数据随机分布，使每次分成的两个子区间中的元素个数大致相等时，递归树高度为log2n，快速排序呈现最好情况，即最好情况下的时间复杂度为O(nlog2n)。快速排序算法的平均时间复杂度也是O(nlog2n)。所以快速排序是一种高效的算法，STL中的sort()算法就是采用快速排序方法实现的。3.2.2归并排序
归并排序的基本思想是首先将a［0..n-1］看成n个长度为1的有序表，将相邻的k(k≥2)个有序子表成对归并，得到n/k个长度为k的有序子表； 然后再将这些有序子表继续归并，得到n/k2个长度为k2的有序子表，如此反复进行下去，最后得到一个长度为n的有序表。由于整个排序结果放在一个数组中，所以不需要特别地进行合并操作。若k=2，即归并是在相邻的两个有序子表中进行的，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。这里仅讨论二路归并排序算法，二路归并排序算法主要有两种，下面一一讨论。1. 自底向上的二路归并排序算法自底向上的二路归并算法采用归并排序的基本原理，第1趟归并排序时将待排序的表a［0..n-1］看作是n个长度为1的有序子表，将这些子表两两归并，若n为偶数，则得到n/2个长度为2的有序子表； 若n为奇数，则最后一个子表轮空(不参与归并)，故本趟归并完成后，前n/2-1个有序子表长度为2，但最后一个子表长度仍为1； 第2趟归并则是将第1趟归并所得到的n/2个有序子表两两归并，如此反复，直到最后得到一个长度为n的有序表为止。首先设计算法Merge()用于将两个有序子表归并为一个有序子表。设两个有序子表存放在同一个表中相邻的位置上，即a［low..mid］(有mid-low 1个元素)、a［mid 1..high］(有high-mid个元素)，先将它们合并到一个临时表tmpa［0..high-low］中，在合并完成后将tmpa复制到a中。其归并过程是循环从两个子表中顺序取出一个元素进行比较，并将较小者放到tmpa中，当一个子表元素取完时将另一个子表中余下的部分直接复制到tmpa中。这样tmpa是一个有序表，再将其复制到a中。其次，设计算法MergePass()通过调用Merge()算法解决一趟归并问题。在某趟归并中，设各子表长度为length(最后一个子表的长度可能小于length)，则归并前a［0..n-1］中共nlength个有序子表，即a［0..1ength-1］、a［length..2length-1］、…、anlengthlength..n-1。调用Merge()一次将相邻的一对子表进行归并，另外需要对表的个数可能是奇数以及最后一个子表的长度小于length这两种特殊情况进行处理： 若子表的个数为奇数，则最后一个子表无须和其他子表归并(即本趟轮空)； 若子表的个数为偶数，则要注意到最后一对子表中后一个子表的区间上界是n-1。最后，对于含有n个元素的序列a，设计算法MergeSort()调用MergePass()算法log2n次实现二路归并排序。二路归并排序的分治策略如下： 循环log2n次，length依次取1、2、…、log2n，每次执行以下步骤。(1) 分解： 将原序列分解成length长度的若干个子序列。(2) 求解子问题： 对相邻的两个子序列调用Merge算法合并成一个有序子序列。(3) 合并： 由于整个序列存放在数组a中，排序过程是就地进行的，合并步骤不需要执行任何操作。 例如，对于(2，5，1，7，10，6，9，4，3，8)序列，其排序过程如图3.4所示，图中方括号内是一个有序子序列。
图3.4自底向上的二路归并排序过程
实现二路归并排序的完整程序如下：
#include
#include
void disp(int a［］,int n)//输出a中的所有元素
{int i;
for (i=0;iprintf(“%d “,a［i］);
printf(“＼n”);
}
void Merge(int a［］,int low,int mid,int high)
//将a［low..mid］和a［mid 1..high］两个相邻的有序子序列归并为一个有序子序列a［low..high］
{int *tmpa;
int i=low,j=mid 1,k=0; //k是tmpa的下标,i、j分别为两个子表的下标
tmpa=(int *)malloc((highlow 1)*sizeof(int));
while (i<=mid && j<=high) //在第1个子表和第2个子表均未扫描完时循环
if (a［i］<=a［j］) //将第1个子表中的元素放入tmpa中
{tmpa［k］=a［i］;
i ;k ;
}
else //将第2个子表中的元素放入tmpa中
{tmpa［k］=a［j］;
j ;k ;
}
while (i<=mid) //将第1个子表余下的部分复制到tmpa
{tmpa［k］=a［i］;
i ;k ;
}
while (j<=high) //将第2个子表余下的部分复制到tmpa
{tmpa［k］=a［j］;
j ;k ;
}
for (k=0,i=low;i<=high;k ,i ) //将tmpa复制回a中
a［i］=tmpa［k］;
free(tmpa); //释放临时空间
}
void MergePass(int a［］,int length,int n)//一趟二路归并排序
{int i;
for (i=0;i 2*length-1Merge(a,i,i length-1,i 2*length-1);
if (i length-1 //余下两个子表,后者的长度小于length
Merge(a,i,i length-1,n-1); //归并这两个子表
}
void MergeSort(int a［］,int n) //二路归并算法
{int length;
for (length=1;lengthMergePass(a,length,n);
}
void main()
{int n=10;
int a［］={2,5,1,7,10,6,9,4,3,8};
printf(“排序前:”); disp(a,n);
MergeSort(a,n);
printf(“排序后:”); disp(a,n);
}
【算法分析】对于上述二路归并排序算法，当有n个元素时需要log2n趟归并，每一趟归并，其元素比较次数不超过n-1，元素移动次数都是n，因此二路归并排序的时间复杂度为O(nlog2n)。2. 自顶向下的二路归并排序算法上述自底向上的二路归并算法虽然效率较高，但可读性较差。另一种是采用自顶向下的方法设计，算法更为简洁，属典型的二分法算法。设归并排序的当前区间是a［low..high］，则递归归并的步骤如下。(1) 分解： 将当前序列a［low..high］一分为二，即求mid=(low high)/2，分解为两个子序列a［low..mid］和a［mid 1..high］。(2) 子问题求解： 递归地对两个子序列a［low..mid］和a［mid 1..high］二路归并排序。其终结条件是子序列的长度为1或者0(因为一个元素的子表或者空表可以看成有序表)。(3) 合并： 与分解过程相反，将已排序的两个子序列a［low..mid］和a［mid 1..high］归并为一个有序序列a［low..high］。对应的二路归并排序算法如下：
void MergeSort(int a［］,int low,int high)//二路归并算法
{int mid;
if (low //子序列有两个或两个以上元素
{mid=(low high)/2; //取中间位置
MergeSort(a,low,mid); //对a［low..mid］子序列排序
MergeSort(a,mid 1,high); //对a［mid 1..high］子序列排序
Merge(a,low,mid,high); //将两个子序列合并,见前面的算法
}
}
例如，对于(2，5，1，7，10，6，9，4，3，8)序列，其排序过程如图3.5所示，图中圆括号内的数字指出操作顺序。
图3.5自顶向下的二路归并排序过程
【算法分析】设MergeSort(a，0，n-1)算法的执行时间为T(n)，显然Merge(a，0，n/2，n-1)合并操作的执行时间为O(n)，所以得到以下递推式：
T(n)=1当n=1时
T(n)=2T(n/2) O(n)当n>1时
容易推出T(n)=O(nlog2n)。3.3求解查找问题3.3.1查找最大和次大元素
【问题描述】对于给定的含有n个元素的无序序列，求这个序列中最大和次大的两个不同元素。【问题求解】对于无序序列a［low..high］，采用分治法求最大元素max1和次大元素max2的过程如下： (1) 若a［low..high］中只有一个元素，则max1=a［low］，max2=-INF(-∞)。(2) 若a［low..high］中只有两个元素，则max1=max{a［low］，a［high］}，max2=min{a［low］，a［high］}。(3) 若a［low..high］中有两个以上元素，按中间位置mid=(low high)/2划分为a［low..mid］和a［mid 1..high］两个区间(注意左区间包含a［mid］元素)。求出左区间的最大元素lmax1和次大元素lmax2，求出右区间的最大元素rmax1和次大元素rmax2。若lmax1>rmax1，则max1=lmax1，max2=max{lmax2，rmax1}； 否则max1=rmax1，max2=max{lmax1，rmax2}。例如，对于a［0..4］={5，2，1，4，3}，mid=(0 4)/2=2，划分为左区间a［0..2］={5，2，1}，右区间a［3..4］={4，3}。在左区间中求出lmax1=5，lmax2=2，在右区间中求出rmax1=4，rmax2=3。所以max1=max{lmax1，rmax1}=5，max2=max{lmax2，rmax1}=4。对应的算法如下：
void solve(int a［］,int low,int high,int &max1,int &max2)
{if (low==high)//区间中只有一个元素
{max1=a［low］;
max2=-INF;
}
else if (low==high-1) //区间中只有两个元素
{max1=max(a［low］,a［high］);
max2=min(a［low］,a［high］);
}
else //区间中有两个以上元素
{int mid=(low high)/2;
int lmax1,lmax2;
solve(a,low,mid,lmax1,lmax2); //左区间求lmax1和lmax2
int rmax1,rmax2;
solve(a,mid 1,high,rmax1,rmax2); //右区间求rmax1和rmax2
if (lmax1>rmax1)
{max1=lmax1;
max2=max(lmax2,rmax1); //lmax2、rmax1中求次大元素
}
else
{max1=rmax1;
max2=max(lmax1,rmax2); //lmax1、rmax2中求次大元素
}
}
}
【算法分析】对于solve(a，0，n-1，max1，max2)调用，其比较次数的递推式如下：
T(1)=T(2)=1
T(n)=2T(n/2) 1//合并的时间为O(1)
可以推导出T(n)=O(n)。3.3.2折半查找
折半查找又称二分查找，它是一种效率较高的查找方法。但是折半查找要求查找序列中的元素是有序的，为了简单，假设是递增有序的。折半查找的基本思路： 设a［low..high］是当前的查找区间，首先确定该区间的中点位置mid=(low high)/2； 然后将待查的k值与a［mid］.key比较。(1) 若k==a［mid］.key，则查找成功并返回该元素的物理下标。(2) 若k
评论
还没有评论。