下载文档原格式
算法分析与设计大作业摘要：本文以算法分析与设计为主题，对算法的概念、分析和设计进行了探讨。
首先介绍了算法的概念和基本特征，其次分析了算法的效率和复杂度，并介绍了常用的算法复杂度表示方法。
然后，通过实例分析了几种常用的排序算法的性能与复杂度，并对它们进行了比较。
最后，总结了算法分析与设计的重要性，并提出了进一步研究的方向。
一、引言随着计算机技术的快速发展，算法分析与设计成为计算机领域中的重要研究方向。
算法是指解决特定问题的具体步骤和方法，是计算机科学的核心和基础。
算法的效率和复杂度对计算机的性能和运行时间有着直接的影响，因此算法的分析和设计非常重要。
二、算法的概念和特征算法是指在有限的时间内解决特定问题的一种方法。
它具有以下特征：输入、输出、确定性、有穷性和可行性。
输入是指算法接受的问题的数据或信息，输出是指算法求解得到的问题的解。
确定性是指算法在任何情况下都能够得到相同的结果。
有穷性是指算法在执行有限的步骤后能够终止。
可行性是指算法的每一步都是可行的，即能够被计算机执行。
三、算法的效率和复杂度算法的效率是指算法解决问题所需要的时间和空间资源的多少。
算法的复杂度是用来描述算法执行过程中所需要的资源的多少。
常用的算法复杂度表示方法有时间复杂度和空间复杂度。
时间复杂度表示算法的执行时间与输入规模之间的关系，用大写O表示。
空间复杂度表示算法所需的空间资源与输入规模之间的关系，用大写S表示。
四、常用的排序算法及性能与复杂度分析1.插入排序插入排序是一种简单直观的排序算法。
它的基本思想是将未排序的元素逐个插入到已排序的序列中。
插入的过程中，需要比较和移动元素的次数与未排序序列中的元素个数相关，因此时间复杂度为O(n^2)。
空间复杂度为O(1)。
2.冒泡排序冒泡排序是一种重复比较相邻元素并交换位置的排序算法。
它的基本思想是两两比较相邻元素，如果顺序错误则交换位置。
冒泡的过程中，需要进行n-1次的比较和交换操作，因此时间复杂度为O(n^2)。
算法分析与设计大作业班级： 12信科姓名：郭倩南学号： 1242155105完成日期： 2015-6-4指导教师：陈平序号选定题目所用算法设计技术1数字三角形问题动态规划2集合划分问题分治法回溯法3求子集问题评分：大作业报告1、数字三角形问题一、问题描述对于给定的由n行数字组成的数字三角形，计算从三角形的底至顶的路径经过的数字和的最大值。
如：73 88 1 02 7 4 44 5 2 6 5二、实验内容与实验步骤实验内容:输入数据的第1 行是数字三角形的行数n，1<=n<=100。
接下来n行是数字三角形各行中的数字。
所有数字在0..99之间实验步骤:1、首先证明该问题满足最优化原理最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。
简而言之，一个最优化策略的子策略总是最优的。
2、建立动态规划函数3、填表三、实验环境Window7系统，vc++6.0软件四、问题分析由观察数字三角形可知，从数字三角形的顶层出发，下一层选择向左还是向右取决于两个4层数字三角形的最大数字和，而对于第四层的决定取决于第三层的最大数字和，依次类推，可知该问题是多阶段决策最优化问题，并且划分出来的子问题是相互重叠的，所以该问题采用动态规划法解决动态规划：与分治法相似，把问题分解按层次分成子问题，直到可以直接求解的子问题，然后一级一级地向上求解。
与分治法的出别在于：动态规划适用有许多重复子问题出现的问题，它保存已求出问题的解。
73 8 3 88 1 0 8 1 1 02 7 4 4 2 7 4 7 4 4 4 5 2 6 5 4 5 2 6 5 2 6 5一个五层数字三角形子问题〔1〕子问题〔2〕五、问题解决〔1〕根据对问题的分析，写出解决方法。
1、证明：S,S1,S2,..Sn,t是从S到t的一条数字和最大的路径，从源点S开始，设从S到下一段的顶点S1已经求出，如此问题转化为求从S1到t的数字和最大的路径，显然S1，S2，...Sn,t一定构成一条从S1到t的数字和最大值的路径，如假如不然，设S1，r1,r2,....rq,t是一条数字和最大的路径，如此S,S1，r1,r2,....rq,t的路径经过数字和的最大值比S,S1，S2，...Sn,t的路径数字和更大，从而导致矛盾，所以数字三角形问题满足最优性原理。
题目作业调度问题及算法分析学院名称：计算机与信息工程学院专业名称：计算机科学与技术目录《算法设计与分析》课程大作业 (1)一．动态规划算法解决流水作业调度 (3)1、问题描述 (3)2、算法分析 (3)3. 算法的描述 (4)4、部分算法实现 (5)5. 运行结果 (6)6、时空效率分析 (6)二．贪心算法解多机调度问题 (6)1、问题描述 (6)2、算法分析 (7)3.部分算法实现 (7)4.计算复杂性分析 (8)5. 运行结果 (9)三．回溯法解决批作业调度问题 (9)1.问题描述 (9)2.算法思想 (10)3. 部分算法实现 (11)4.运行结果 (12)5.时间复杂性分析 (12)四．作业调度算法比较 (12)五．课程学习总结 (13)摘要：在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。
把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。
关键词：作业调度；动态规划；贪心算法；回溯法；一．动态规划算法解决流水作业调度1、问题描述给定n 个作业，每个作业有两道工序，分别在两台机器上处理。
一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。
一个作业只有在机器1上的处理完成以后才能由机器2处理。
假设已知作业i 在机器j 上需要的处理时间为t[i,j]。
流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。
2、算法分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。
在一般情况下，机器M2上会有机器空闲和作业积压2种情况。
在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。
将这种情况下完成S 中作业所需的最短时间记为T(S,t)。
排序算法复杂性分析一健鹏明欢我们重承诺，本作业的容均为原创，没有任何抄袭他人成果的行为，也不存在他人代写作业和程序的行为。
引用他人成果或公开资料的部分都已经按照正确的格式在参考文献中标出。
作者签字得分统计学生填写老师填写学号工作所占比例得分分别得分健20131401鹏20131400明欢20130711摘要本文通过三种简单排序-插入、冒泡和选择排序算法并运用C++语言编程实现，以计算简单排序算法复杂度。
首先，利用不同规模下随机产生的不同序列，计算三种排序方法下的元运算-比较、交换、移动的次数来定量刻画排序算法的时间复杂度，即序列规模与元运算次数的关系，得到三种算法的时间复杂度均为，这说明这三种排序算法具有相同时间复杂度，并且实现简单，所以也归为一类简单排序算法。
其次，采用统一规模下的不同排列顺序，主要是两个极端序-顺序、逆序的情况下分析三种算法的时间复杂度，得到算法的最好时间复杂度为，最坏时间复杂度为，反映出不同顺序的序列导致的排序算法时间复杂度的巨大差异性，并且插入、冒泡排序与选择排序之间的优劣也逐渐显现出来，主要是由于逆序对的数目导致交换次数变化的缘故。
最后，本文将作为其他排序算法的时间复杂度作为后续扩展部分，以待完善。
本文将围绕以下两个问题进行讨论分析:1）设计一个程序，程序的输入为n个（n必须要从键盘输入）0到10000的正整数（正整数可以是随机产生），输出为对这n个数进行从小到大排序后的序列。
排序方法分别使用插入排序、冒泡排序和选择排序。
2）以两个数比较、两个数交换、移动一个数为基本计算单位，测试你所编写的程序对于n=100,500,1000,2000四种输入规模的时间复杂度。
一、算法复杂度1.1算法复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
Linux大作业的算法分析怎么写Linux大作业分析框架1、以算法输入规模n作为参数进行分析算法效率2、时间复杂度：找出基本操作O(1)，再计算它的运行次数(忽略乘法常量，仅关注增长次数)3、增长次数：log2n4、最差、平均和最佳效率均是指输入规模为n时候的效率(平均效率可以引用已知的推到结果)主要概括分析框架：1、算法的时间效率和空间效率都用输入规模的函数进行度量。
2、用算法的基本操作的执行次数来度量时间效率，用算法消耗的额外单位的数量来度量空间单位3、在输入规模相同的情况下，有写算法的效率会有显著的差异，对于这类算法需要分析最差、平均和最佳效率4、框架主要关心：输入规模趋向于无限大的情况下它的效率问题渐近符号和基本效率类型1、O(g(n))是增长次数&lt;=c*g(n)的函数集合，上阶2、Ω(g(n))是增长次数&gt;=c*g(n)的函数集合，下阶3、θ(g(n))是增长次数=c*g(n)的函数集合，同阶可以利用极限进行比较增长次数(洛必达法则)算法整体效率是由具有较大增长次数的部分所决定的。
非递归问题的数学分析的通用方案1、决定哪个参数表示输入规模的度量标准2、找出算法的基本操作3、检查基本操作的执行次数是否只依赖于输入规模，如果它还依赖于一些其他的特性(例如：元素在数组中的位置等)则分析最差、平均和最佳效率4、建立一个算法基本操作执行次数的求和表达式(有可能是递推表达式)5、利用求和运算的标准运算或者法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数递归问题的数学分析的通用方案1、决定哪个参数表示输入规模的度量标准2、找出算法的基本操作3、检查基本操作的执行次数是否只依赖于输入规模，如果它还依赖于一些其他的特性(例如：元素在数组中的位置等)则分析最差、平均和最佳效率4、对于算法基本操作执行次数，建立一个递推关系以及相应的初始条件。
5、解这个递推式，或者至少确定它的增长次数。
课号：____CK5J08A ___ 课名：_____算法设计与分析______教师: ________________期末大作业要求：在以下几种方式中任选一种一．算法实际应用题任务要求：1．完成一个有一定实用性的程序，其中包含稍复杂的算法模块，算法输入和输出必须显示在图形界面上，最好能把算法运行过程展现在图形界面上。
2．撰写算法设计报告，描述算法设计流程，分析算法效率。
3．进行答辩。
评分标准：1．图形界面的操作方便性与对算法的展现程度(30分)2．算法的复杂程度和算法效率和实用性(30分)3．算法设计流程的解释的清晰度和算法效率分析的准确度(30分)4．答辩10分，采用教师提问学生回答和解释的形式，学生若不能自圆其说、对自己设计的算法流程也讲不清楚，则判定为抄袭，整个大作业为0分。
参考题目：1．算242．倒油3．趣味算式4．马步问题5．单源最短路径6．最小生成树7．工作分配8．2*2*2魔方9．长江游艇10．推箱子11．华容道12．文件搜索13．………..二．ACM算法设计题任务要求：1.完成2道及2道以上ACM算法设计题，题目由教师给定并公布在OJ系统中，学生限定时间内(2个小时)，在其中选做2题以上，正确性也由OJ系统判定，并参照OJ系统的标准，形成排名。
完成数量不到2题的，不管排名如何，整个大作业都判定为不及格。
2.为所完成的每道题目撰写解题报告，描述设计思路与流程，分析课号：____CK5J08A ___ 课名：_____算法设计与分析______教师: ________________程序的时空效率。
评分标准：1.算法设计能力(60分)，主要根据OJ系统中的排名来评定，部分提交的题目有抄袭嫌疑的学生，教师对其进行质询答辩，采用问答形式，学生若对其提交正确的任何题目，无法通过质询答辩，则判定为抄袭，整个大作业为0分。
2.算法表述与分析能力(40分)，根据提交的解题报告中，对算法流程的描述的清晰程度，对算法时空效率的分析的准确程度，进行评定。
算法剖析演习题（一）一.选择题1.二分搜刮算法是应用（ A ）实现的算法.A.分治计谋B.动态计划法C.贪婪法D.回溯法2.下列不是动态计划算法根本步调的是（ A ）.A.找出最优解的性质B.构造最优解C.算出最优解D.界说最优解3．下列算法中平日以自底向上的方法求解最优解的是（ B ）.A.备忘录法B.动态计划法C.贪婪法D.回溯法4.权衡一个算法利害的尺度是（ C ）.A 运行速度快B 占用空间少C 时光庞杂度低D 代码短5.以下不成以应用分治法求解的是（ D ）.A 棋盘笼罩问题B 选择问题C 归并排序D 0/1背包问题6.实现轮回赛日程表应用的算法是（ A ）.A.分治计谋B.动态计划法C.贪婪法D.回溯法7.备忘录办法是那种算法的变形.（ B ）A.分治法B.动态计划法C.贪婪法D.回溯法8．最长公共子序列算法应用的算法是（ B ）.A.分支界线法B.动态计划法C.贪婪法D.回溯法9．实现棋盘笼罩算法应用的算法是（ A ）.A.分治法B.动态计划法C.贪婪法D.回溯法10. 矩阵连乘问题的算法可由（B）设计实现.A.分支界线算法B.动态计划算法C.贪婪算法D.回溯算法11.Strassen矩阵乘法是应用（ A ）实现的算法.A.分治计谋B.动态计划法C.贪婪法D.回溯法12.应用分治法求解不须要知足的前提是（A ）.A 子问题必须是一样的B 子问题不克不及够反复C 子问题的解可以归并D 原问题和子问题应用雷同的办法解13.下列算法中不克不及解决0/1背包问题的是（A ）A 贪婪法B 动态计划C 回溯法D 分支限界法14．实现归并排序应用的算法是（ A ）.A.分治计谋B.动态计划法C.贪婪法D.回溯法15．下列是动态计划算法根本要素的是（ D ）.A.界说最优解B.构造最优解C.算出最优解D.子问题重叠性质16．下列算法中平日以自底向下的方法求解最优解的是（ B ）.A.分治法B.动态计划法C.贪婪法D.回溯法17.归并排序算法是应用（ A ）实现的算法.A.分治计谋B.动态计划法C.贪婪法D.回溯法18．实现大整数的乘法是应用的算法（ C ）.A.贪婪法B.动态计划法C.分治计谋D.回溯法19. 实现最大子段和应用的算法是（ B ）.A.分治计谋B.动态计划法C.贪婪法D.回溯法20. 一个问题可用动态计划算法或贪婪算法求解的症结特点是问题的（ B ）.A.重叠子问题B.最优子构造性质C.贪婪选择性质D.界说最优解21.实现最长公共子序列应用的算法是（ B ）.A.分治计谋B.动态计划法C.贪婪法D.回溯法二.填空题时光庞杂性和空间庞杂性之分.2.程序是算法用某种程序设计说话的具体实现.3.算法的“肯定性”指的是构成算法的每条指令是清楚的,无歧义的.4.矩阵连乘问题的算法可由动态计划设计实现.5.算法是指解决问题的一种办法或一个进程.6.从分治法的一般设计模式可以看出,用它设计出的程序一般是递归算法.7.矩阵连乘问题的算法可由动态计划设计实现.8. 动态计划算法的根本思惟是将待求解问题分化成若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解.9.算法是由若干条指令构成的有穷序列,且要知足输入.输出 .肯定性和有限性四条性质.10.大整数乘积算法是用分治法来设计的.11.快速排序算法是基于分治计谋的一种排序算法.12.动态计划算法的两个根本要素是. 性质和性质 .范围有关.划分的对称性 .15.出自于“均衡子问题”的思惟,平日分治法在朋分原问题,形成若干子问题时,这些子问题的范围都大致雷同.16.应用二分搜刮算法在n个有序元素表中搜刮一个特定元素,在最佳情况下,搜刮的时光庞杂性为O（）,在最坏情况下,搜刮的时光庞杂性为O（logn）.17.已知一个分治算法消耗的盘算时光T(n),T(n)知足如下递归方程：解得此递归方可得T(n)= O（nlogn）.18.动态计划算法有一个变形办法备忘录办法.这种办法不合于动态计划算法“自底向上”的填充偏向,而是“自顶向下”的递归偏向,为每个解过的子问题树立了备忘录以备须要时检讨,同样也可防止雷同子问题的反复求解.19.递归的二分查找算法在divide阶段所花的时光是O(1),conquer阶段所花的时光是T(n/2) ,算法的时光庞杂度是O( log n).20.用动态计划算法盘算矩阵连乘问题的最优值所花的时光是O(n3), 子问题空间大小是O(n2) .21.一个算法的好坏可以用（时光庞杂度）与（空间庞杂度）与来权衡.22.直接或间接地挪用自身的算法称为（递归算法）.23.q 记号在算法庞杂性的暗示法中暗示（渐进确界或紧致界）.24.在分治法中,使子问题范围大致相等的做法是出自一种（均衡子问题）的思惟.25.动态计划算法实用于解（具有某种最优性质）问题.26.最优子构造性质的寄义是（问题的最优解包含其子问题的最优解）.27.按照符号O的界说O(f)+O(g)等于O(max{f(n),g(n)}).28.二分搜刮技巧是应用（分治）计谋的典范例子.29.动态计划算法中,平日不合子问题的个数随问题范围呈（多项式）级增加.30.（最优子构造性质）和（子问题重叠性质）是采取动态计划算法的两个根本要素.三.算法填空1.最大子段和: 动态计划算法int MaxSum(int n, int a[]){int sum=0, b=0; //sum存储当前最大的b[j], b存储b[j]for(int j=1; j<=n; j++) {if（b>0） b+=a[j] ;else b=a[i]; //一旦某个区段和为负,则从下一个地位累和if (b>sum) sum=b ;}return sum;}template<class Type>void QuickSort (Type a[], int p, int r){if (p<r) {int q=Partition(a,p,r);QuickSort（a,p,q-1）; //对左半段排序QuickSort(a,q+1,r); //对右半段排序}}四.简答题1.写出下列庞杂性函数的偏序关系（即按照渐进阶从低到高排序）：2.将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分离求出这两段的最大子段和,则a[1:n]的最大子段和有哪三种情况？3.请解释动态计划办法为什么须要最优子构造性质.最优子构造性质是指大问题的最优解包含子问题的最优解. 动态计划办法是自底向上盘算各个子问题的最优解,即先盘算子问题的最优解,然后再应用子问题的最优解构造大问题的最优解,是以须要最优子构造4.设计动态计划算法的重要步调是怎么的？请简述.参考解答：（1）找出最优解的性质,并刻划其构造特点.(6分) （2）递归地界说最优值.（3）以自底向上的方法盘算出最优值. （4）依据盘算最优值时得到的信息,构造最优解.5.分治法所能解决的问题一般具有哪几个特点？请简述.参考解答：（1）该问题的范围缩小到必定的程度就可以轻易地解决;(6分) （2）该问题可以分化为若干个范围较小的雷同问题,即该问题具有最优子构造性质;（3）应用该问题分化出的子问题的解可以归并为该问题的解;（4）原问题所分化出的各个子问题是互相自力的,即子问题之间不包含公共的子问题.6.算法的要特点是什么？参考解答：肯定性.可实现性.输入.输出.有穷性7、算法剖析的目标是什么？参考解答：剖析算法占用盘算机资本的情况,对算法做出比较和评价,设计出额更好的算法.8.算法的时光庞杂性与问题的什么身分相干？参考解答：算法的时光庞杂性与问题的范围相干,是问题大小n的函数.9.算法的渐进时光庞杂性的寄义？参考解答：当问题的范围n趋势无限大时,影响算法效力的重要身分是T(n)的数目级,而其他身分仅是使时光庞杂度相差常数倍,是以可以用T(n)的数目级(阶)评价算法.时光庞杂度T(n)的数目级(阶)称为渐进时光庞杂性.10简述渐进时光庞杂性上界的界说.参考解答：T(n)是某算法的时光庞杂性函数,f(n)是一简略函数,消失正整数No和C,n〉No,有T(n)<f(n),这种关系记作T(n)=O(f(n)).11快速排序算法最坏情况下须要若干次比较运算？参考解答：最坏情况下快速排序退化成冒泡排序,须要比较n2次.12阐述归并排序的分治思绪.参考解答：讲数组一分为二,分离对每个聚集单独排序,然后将已排序的两个序列归并成一个含n个元素的分好类的序列.假如朋分后子问题还很大,则持续分治,直到一个元素.13快速排序的根本思惟是什么.参考解答：快速排序的根本思惟是在待排序的N个记载中随意率性取一个记载,把该记载放在最终地位后,数据序列被此记载分成两部分.所有症结字比该记载症结字小的放在前一部分,所有比它大的放置在后一部分,并把该记载排在这两部分的中央,这个进程称作一次快速排序.之后反复上述进程,直到每一部分内只有一个记载为止.14分治法的根本思惟是什么？将一个范围为N的问题分化为K个范围较小的子问题,这些子问题互相自力且与原问题性质雷同.求出子问题的解,就可得到原问题的解.即一种分目标完成程序算法,简略问题可用二分法完成.15设计动态计划算法的重要步调？参考解答：（1）找出最优解的性质,并刻划其构造特点.(6分) （2）递归地界说最优值.（3）以自底向上的方法盘算出最优值. （4）依据盘算最优值时得到的信息,构造最优解.16分治法与动态计划法的异同配合点：将待求解的问题分化成若干子问题,先求解子问题,然后再从这些子问题的解得到原问题的解.不合点：1.合适于用动态计划法求解的问题,分化得到的各子问题往往不是互相自力的;而分治法中子问题互相自力.2.动态计划法用表保管已求解过的子问题的解,再次碰着同样的子问题时不必从新求解,而只需查询答案,故可获得多项式级时光庞杂度,效力较高;而分治法中对于每次消失的子问题均求解,导致同样的子问题被反复求解,故产生指数增加的时光庞杂度,效力较低.17分治法所能解决的问题一般具有的几个特点？参考解答：（1）该问题的范围缩小到必定的程度就可以轻易地解决;(6分) （2）该问题可以分化为若干个范围较小的雷同问题,即该问题具有最优子构造性质;（3） 应用该问题分化出的子问题的解可以归并为该问题的解;（4）原问题所分化出的各个子问题是互相自力的,即子问题之间不包含公共的子问题.五.算法设计题1.【最长上升子序列问题】—— 提醒：此题可采取动态计划算法实现对于给定的一个序列12(,,,)N a a a ,11000N ≤≤.我们可以得到一些递增上升的子序列12(,,,)i i iK a a a ,这里121K i i i N ≤<<<≤.比方,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等.这些子序列中最长的长度是4,比方剂序列(1, 3, 5, 8).你的义务：就是对于给定的序列,求出最长上升子序列的长度.请求写出你设计的算法思惟及递推函数的公式表达..2.【Gray码构造问题】——提醒：此题可采取分治递归算法实现问题描写：“格雷码”是一个长度为n2的序列,知足：（a）每个元素都是长度为n比特的串（b）序列中无雷同元素（c）持续的两个元素正好只有1个比特不合例如：n=2时,格雷码为{00,01,11,10}.Gray码是一种编码,这种编码可以防止在读取时,因各数据位时序上的差别造成的误读.格雷码在工程上有普遍应用.但格雷码便利于运算,请你设计一种构造办法,输入长度序列n,输出格雷码（你只要做出一种构造计划即可,格雷码其实不独一）.3.如今有8位运发动要进行网球轮回赛,要设计一个知足以下请求的比赛日程表：（1）每个选手必须与其他选手各赛一次;（2）每个选手一天只能赛一次;（3）轮回赛一共进行n – 1天.请应用分治法的思惟,给这8位运发动设计一个合理的比赛日程. 4.对于矩阵连乘所需起码数乘次数问题,其递归关系式为：个中m[i,j]为盘算矩阵连乘Ai…Aj所需的起码数乘次数,p i-1为矩阵Ai的行,p为矩阵Ai的列.现有四个矩阵,个中各矩阵维数分i离为：请依据以上的递归关系,盘算出矩阵连乘积A1A2A3A4所须要的起码数乘次数.5.有如许一类特别0-1背包问题：可选物品重量越轻的物品价值越高.n=6,c=20,P=（4,8,15,1,6,3）,W=（5,3,2,10,4,8）.个中n为物品个数,c为背包载重量,P暗示物品的价值,W暗示物品的重量.请问对于此0-1背包问题,应若何选择放进去的物品,才干使到放进背包的物品总价值最大,能获得的最大总价值若干？6.归并排序算法对下列实例排序,写出算法履行进程.A=(48,12,61,3,5,19,32,7)7.规矩证实： O(f(n))+O(g(n)) = O(max{f(n),g(n)})8.给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x,返回其在数组中的地位,假如未找到返回-1.写出二分搜刮的算法,并剖析当时光庞杂度.9.应用分治算法写出归并排序的算法,并剖析当时光庞杂度。
《算法设计与分析大作业报告》班级：学号：姓名：分治法大作业报告问题陈述：编程实现归并排序算法和快速排序算法，输出排序结果。
输入10组相同的数据，验证排序结果和完成排序的比较次数。
分治法基本思想：分治法的基本思想是将问题分解成若干个子问题，然后求解子问题。
子问题较原问题要容易些，先得出子问题的解，由此得出原问题的解，这就是所谓“分而治之”的思想。
算法描述：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。
那末，对于这类问题分治法是十分有效的。
本实验就是通过归并排序和快速排序来体现分治的思想。
1.归并排序的思想：将A（1），……，A（N）分成两个集合，对每个集合单独分类，然后将已分类的两个序列归并成一个含N个元素分好类的元素2.快速排序的思想：选取A的某个元素做为划分元素，然后将其他元素重新排列，使在划分元素以前出现的元素都小于或等于它，在划分元素之后出现的划分元素都大于等于它。
程序代码：#include <stdio.h>#include <time.h>#include <stdlib.h>void MergeSort(int *data,int x,int y,int *temp){ int p,q,m,i=x;if (y-x>1){m = x+(y-x)/2;p = x;q = m;MergeSort(data,x,m,temp);MergeSort(data,m,y,temp);while(p<m||q<y){if (q>=y||(p<m&&data[p]<data[q])){temp[i++] = data[p++];}else{temp[i++] = data[q++];}}for(i=x;i<y;i++)data[i] = temp[i]; }}void HoareSort(int *data,int x,int y){int p=x,q=y-1,temp;while(p<q) {while (q>p&&data[q]>=data[p])q--;if (q>p){temp = data[p],data[p] = data[q],data[q] =temp;p++;}while(q>p&&data[p]<=data[q])p++;if (p<q){temp = data[p],data[p] = data[q],data[q] =temp;q--;}if (p==q) {HoareSort(data,x,p);HoareSort(data,p+1,y);}}}int main(){int data[10],i;int temp[10];srand(time(NULL));for (i=0;i<10;i++){ data[i] = rand()%100; }printf("未排序排序的数据为：\n");for (i=0;i<10;i++){printf("%d ",data[i]);}printf("\n");printf("归并排序的顺序为： \n");MergeSort(data,0,10,temp);for (i=0;i<10;i++){printf("%d ",data[i]); }printf("\n");printf("快速排序的顺序为： \n");HoareSort(data,0,10);for (i=0;i<10;i++){printf("%d ",data[i]);}printf("\n");return 0;}运行结果：结论分析：归并排序和快速排序都是递归排序，但是归并排序是稳定的排序方法，快速排序是不稳定的排序方法。
算法理论、教改类题目学习大量相关算法（程序），总结出对应方法的一些特点，将其写成论文形式，并以足够的例子作为佐证。
24.论分治法、动态规划、贪心法的区别 25.论递归程序向非递归程序的转换 26.论应用型本科院校算法课程的教学目标和教学方法 27.论二叉树在计算机科学与技术中的应用 28.数据库索引的算法解释 29.论贪心法的适用范围 30.解空间搜索方法的选择依据 31.分治法算法分析综述
算法应用、算法研究类题目查阅大量相关资料，对相关内容给出初步的结果。
31.基于UCCI的中国象棋对弈引擎开发技术研究 32.五子棋对弈关键技术研究33.黑白棋对弈关键技术研究 34.数独初始局面生成算法研究 35.支持按文件名搜索的索引构造技术研究 36.通用回溯算法演示系统设计 37.通用分支限界算法演示系统设计 38.通用排序算法演示系统设计 39.通用动态规划算法演示系统设计
40.论文阅读和翻译类题目• 给出一个英文文献，用准确的语言将其翻译为中文，不需要逐字逐句翻译，但主要观点、算法思想和算法过程表述清楚、准确、充分。
格式要求• 论文正文中不得出现大段代码（超过10行）• 标题样式需规范• 参考文献不低于10篇，参考文献格式和标注位置须规范。
最接近点对问题问题此问题分为一维，二维，三维的情况1. 一维: 给定直线上n 个点，找其中一对点，使得在n 个点组成的所有点对中，该点对间的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。
2. 二维：给定平面上n 个点，找其中一对点，使得在n 个点组成的所有点对中，该点对间的距离最小，这是我们这一问题的重点3. 三维：给定空间上n 个点，找其中一对点，使得在n 个点组成的所有点对中，该点对间的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。
基本思想由于该问题的基本解法是去考察每个点和其他所有点的距离。
因此它的时间复杂度是2()O n ,这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。
1. 因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算： 把直线分成两部分, 1s 2s ,分别求出其最接近点的距离1d 2d 。
但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。
2. 鉴于此，二维的也可以用此方法进行计算：把待计算的点s 分成两部分1s 2s ，分别求出其最接近点的距离1d 2d 。
但1d 2d 最小的未必是s 中的最小距离d ，它有可能是1s 中的一个点和2s 中的一个点组成的最接近点对。
所以还要考虑1s 中的所有点到2s 中的每一个点的距离，一一比较之后得出一个最小值，再和1d 2d 比较，这就得出了最后结果。
3. 接下来是具体算法实现的步骤：1. 把待计算的点s 分成两部分1s 2s :重要的如何去划分，这里采用在二维平面上的中线（用横坐标的最小值加上最大值的平均数）来划分。
2. 分别求出其最接近点的距离1d 2d :这可以用一个递归来完成。
3. 计算1s 中的所有点到2s 中的每一个点的距离：这个问题是此问题的关键。
目录1.1背景和意义 (1)2.1设计的目的和意义 (2)2.2目标与总体方案 (2)2.3设计方法和内容 (2)2.3.1 设计方法 (2)2.3.2 设计内容 (3)2.4设计创新和关键技术 (5)2.4.1设计创新 (5)2.4.2关键技术 (6)2.5结论 (6)致谢 (6)参考文献 (6)附录A 源程序的清单 (7)前言1.1背景和意义算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。
算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。
在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。
算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。
算法和程序之间存在密切的关系。
分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较。
计算机科学及应用活动中，最有挑战性的困难往往就是算法分析。
人们总是根据应用实践的具体需求，抽象出描述简单而严格的一般性计算问题，专门研究设计这些问题的求解算法。
算法设计追求用较低的时间和空间复杂性，计算得到满足要求的解。
在过去的算法设计实践中，人们针对不同领域的问题设计了许多巧夺天工的求解算法；已形成若干之有效的算法分析技术。
而通过学习这门课程，我们学到了许多的算法思想。
在一学期的学习之后，我们就通过本次的课程设计来检验自我的学习情况。
正文2.1设计的目的和意义课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。
提高学生适应实际，实践编程的能力。
通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。
课程设计的意思是培养学生运用所学课程的知识分析解决实际问题的能力；培养学生调查研究、查阅技术文献、资料、手册以及编写技术文献的能力；通过课程设计，要求学生在指导教师的指导下，独立完成设计课题的全部内容，包括：（1）通过调查研究和上机实习，收集和调查有关技术资料。
（2）掌握课程设计的基本步骤和方法。
（3）根据课题的要求进行上机实验调试。
2.2目标与总体方案本次实验设计是内部排序问题，排序又又很多的方法，所以本程序用了switch来选择不不同点排序方法，用了while循环来判断是否退出排序程序，如果不退出则进行case中的一项排序方法对随机产生的数据进行排序。
所有的排序方法都在主函数中有一个入口，然后在每个排序的子函数中对升序和降序再进行一次选择。
排序的每个模块的思路都差不多，只是每个排序方法的实现算法不同。
基本的思路都是随机产生一组无序的数据，然后用一中排序方法的升序或者降序对它进行排序，然后现实每个排序方法的排序过程。
最后现实统计出来时间和空间复杂度。
该排序程序系统用的数据是通过数组进行存储的，先定义了数组的容量，然后随机对数组的每一个元素赋值。
通过排序再把排序后的数据再存入数组中，显示也是通过for循环一个个显示数组中每一个数据元素值。
2.3设计方法和内容2.3.1 设计方法本次实验主要是实现多种排序的方法功能模块一：该模块实现的是直接插入排序方法，直接插入排序的基本思想是：假设待排序的记录存储在数组R[1...n]中，在排序的过程的某一时刻，R被划分成两个子区间R[1...i-1]和R[i...n],其中，前一个为排好序的有序区，而后一个为无序区。
开始时有序表中只有一个元素R[1]，无序区为R[2....n]。
排序过程中，只需要每次从无序区中取出第一个元素，不它插入到有序表区的适当位置，使之成为新的有序区。
依次这样经过n-1次插入后，无序区为空，有序区中包含了全部n个元素，至此，排序完毕。
功能模块二：该模块实现的是简单选择排序方法，直接插入排序的基本思想是：每次从待排序的无序区中选择出关键字最大（最小）的记录，把该记录与该区中的第一个记录交换位置。
初始时，R[1...n]中选出最大或者最小的记录，将它与R[1]交换，R[1]为有序区；第二趟在无序区R[2...n]中选出最大（最小）的记录与R[2]交换，此时R[1,2]为有序区；依次类推，做n-1趟排序后，区间R[1....n]中记录递减（递增）有序。
功能模块三：该模块实现的是堆排序方法，直接插入排序的基本思想是：在排序过程中，将记录数组R[1...n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉数中双亲结点和孩子结点之间的内在关系，在当前无序中选择关键字最大（最小）的记录。
功能模块四：该模块实现的是冒泡排序方法，直接插入排序的基本思想是：通过相邻元素之间的比较和交换，使排序关键字较大（较小）的元素逐渐从底部移向顶部，即从下标较大的元素移向下标较小的元素。
功能模块五：该模块实现的是快速排序方法，直接插入排序的基本思想是：首先在当前无序区R[low...high]中任取一个记录作为排序比较的基准，用此基准将当前无序区划分为两个较小的无序区：R[low...i-1]和R[i+1...high],并使左边的无序区中所有记录的关键字均小于等于基准的关键字，右边的无序区中的所有记录的关键字都大于等于基准的关键字，而基准记录则位于最终排序的位置i上。
这个过程成为一趟快速排序。
当R[low...i]和R[i+1...high]均非空时，分别对它们进行上述的划分过程，直到所有的无序区中的记录均已排好序为止。
功能模块六：该模块实现的是2-路归并排序方法，直接插入排序的基本思想是：将待排序文件看成n个长度为1的有序子文件，把这些子文件两两归并，得到n/2个长度为2（或者最后一个长度为1）的有序子文件；然后再把这n/2个有序文件的子文件两两归并，如此反复，知道最后得到一个长度为n的有序文件为止。
2.3.2 设计内容由于程序段会在后面的附录出现在此就不再将相应程序在此段出现，只给出相应的实验图图2-1 直接插入排序图2-2 单选择排序图2-3 堆排序图2-4 冒泡排序图2-5 快速排序图2-6 2-路归并排序2.4设计创新和关键技术2.4.1设计创新算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。
数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新的排序等。
在本设计程序中，我将平时认为较为简单的排序问题进行了一次简单的集中。
当多种排序方法放到一起后我们更能看出各种方法的优点以及不足。
同时还能在此同时我还在具体的实践中发现、学习很多以前自己还未能掌握的东西。
对于本次实验我个人认为最大的创新是将多种排序方法集中在一起比较，将各中排序方法执行之后我们会对这些排序方法又更多的了解。
在本设计程序中，充分体现了上述的操作，虽然只是运用局部操作，但是仍然起到了关键作用。
使用C语言和C++相结合的方式，使得程序运行更灵活，处理更方便，在表现方式方面得到了创新。
2.4.2关键技术该课程设计的数据结构就是利用数组来对所有的排序进行存储。
由于排序的方法又有多种，所以只是用数组的数据结构存储每次排序的始末状态，不同的方法都可以使用相同点数据结构.在该课设种还多次运用了在算法分析上所学的递归算法以及二分法，这些方法在各个不同的排序方法中都有不同的体现方式。
2.5结论在本次课程设计过程中我学到了很多的知识，首先是用C++编程，以前很少实践，这次一个一个的子函数都是自己想通了算法才开始写的，写完了之后又一点点小小的成就感。
然而不足之处还是又很多，首先是自己编程不够熟悉，也许算法写得过去复杂，在实现功能方面够完善，还有待好好改进。
致谢首先要感谢学校、学院给我提供了这次宝贵的课程设计机会，让我充分锻炼了实际操作能力，把理论和实践联系到了一起，取得了巨大的收获。
同时也要感谢学院提供了良好的设计条件，使我能在规定时间内保质保量的完成这次设计。
本课题在选题及设计过程中都得到陈杰老师的悉心指导，并为我释疑解惑。
在此对陈杰老师表示我深深的谢意。
很高兴能独自完成一个关于c++语言的算法设计。
这次的课程设计不仅我们花去了不少的时间，也让老师操了一番苦心。
在此次设计中遇到了好多的问题，都是经过老师所给的关于课程设计书才明白所用函数的用法，更重要的是以前在上课时，老师讲课细心，而且又很全面。
把需要讲的几乎都讲过。
老师的细心教学，使我们学会了好多关于C++语言以及其他语言的东西。
从而在这次设计中因有这样的知识渊博老师而感到骄傲，并且也谢谢校领导为我们提供机房，让我们有良好的学习环境，最后献上我真诚的谢意。
在此我还要感谢的人还有庄连成同学，是他给我细心分析各种算法思想和用法，我才得以编成了这个精简实用的程序。
在编写程序的过程中，我不仅得到了同学们的热情帮助，还有老师们的大力支持认真阅读书籍，我的能力得到了提高，同时养成了科学、严谨的学习作风和生活习惯，并且通过这次的课程设计也让我们更清楚的认识到这C++语言的功能及用法，深刻体会到了算法是程序设计的灵魂。
在此，我对同学们的热情帮助表示衷心的感谢！同时也对老师的不辞辛苦而表示忠心的感谢！对辛苦为我们指导的老师说声谢谢。
参考文献[1] 朱大铭马绍汉编著.算法设计与分析高等教育出版社[2] 谭浩强编著.C++面向对象程序设计题解与上机指导.北京：[3] 谭浩强编著.C++面向对象程序设计.北京：清华大学出版社[4] 孔令德叶瑶杨慧炯编著.C++程序设计案例精编.中国铁道出版社[5] 甘玲石岩李盘林编著.解析C++面向对象程序设计.清华大学出版社[6] 邓阿奇著.Visual C++ 教程.清华大学出版社[7] 钱能.C++程序设计.清华大学出版社附录A源程序的清单#include <cstdlib>#include <iostream>#define N 11 // 用来存排序用的数据，其中第一个元素经常作为“哨兵”和交换用int sjs[7],kjs[7]; //分别用来描述排序所用的时间和空间性能,从第二个元素开始使用int sum; //用来计排序的次数int sm[N]; //用来作为辅助存储空间，用于2-路归并排序中using namespace std;//函数声明int zjcr(int s[]);int jdxz(int s[]);int ddpx(int s[],int n);int mppx(int s[]);int kspx(int s[],int low,int high);int gbpx(int s[],int sm[],int n);int main(){ cout<<"******************************************************************** *"<<endl;cout<<" 内部排序问题"<<endl; cout<<"*********************************************************************"<< endl;cout<<""<<endl;cout<<" 计算机科学与技术专业12-3 龙森5011208224 "<<endl;int ch,c=1; //其中ch用来标记所选择的排序方法，c用来判断是否推出排序程序while(c!=0){ cout<<"\n============================================================= ========\n"<<endl;cout<<" 0 退出排序程序"<<endl;cout<<" 1 直接插入排序 2 简单选择排序"<<endl;cout<<" 3 堆排序 4 冒泡排序"<<endl;cout<<" 5 快速排序 6 2-路归并排序"<<endl;cout<<"\n=============================================================== ======"<<endl;cout<<"请选择您要用的排序方法：";cin>>ch;//随机产生排序用的数据int s[N];int i;for(i=1;i<=N-1;i++){s[i]=rand()%100;}cout<<"\n随机产生用来排序的原始数据如下："<<endl<<endl;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl<<endl;switch(ch){ case 0:c=0;break;case 1:zjcr(s);break;case 2:jdxz(s);break;case 3:ddpx(s,N-1);break;case 4:mppx(s);break;case 5:kspx(s,1,N-1);break;case 6:gbpx(s,sm,N-1);break;default:cout<<"您的输入不正确，选择的范围是〈0，1，2，3，4，5，6〉，请重新输入："<<endl;}}system("PAUSE");return 0;}//=====================================函数的定义============================================//直接插入排序算法int zjcrs(int s[]){ sum=0;int i,j;for(i=2;i<=N-1;i++){if(s[i]<s[i-1]){s[0]=s[i]; //s[0]作为哨兵for(j=i-1;s[0]<s[j];j--){s[j+1]=s[j];sjs[1]++;}s[j+1]=s[0];}sum++;cout<<"\n"<<"第"<<sum<<"趟排序结果: ";for(int i=1;i<=N-1;i++){cout<<s[i]<<" ";}}kjs[1]=1; //该算法中只有一个辅助存储空间即s[0]cout<<"\n\n该方法的时间复杂度为："<<"O("<<sjs[1]<<"); 空间复杂度为："<<"O("<<kjs[1]<<")"<<endl;return 0;}int zjcr(int s[]) //直接插入排序的主要函数{ cout<<"\n您选择的是: [直接插入排序方法] \n"<<endl;cout<<"\n数据的初始顺序如下: "<<endl;int i;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;sjs[1]=kjs[1]=0; //时空计数清零zjcrs(s);cout<<"\n排序后数据的顺序如下："<<endl;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;return 0;}//简单选择排序算法int jdxzs(int s[]){ sum=0;int i,j,k;for(i=1;i<=N-1;i++){ k=i ; //记录关键字最小的记录位置for(j=i+1;j<=N-1;j++){if(s[j]<s[k])k=j; //更新最小记录的位置}if(k!=i)//与第i个记录进行交换{s[0]=s[i];s[i]=s[k];s[k]=s[0];sjs[2]++;}sum++;cout<<"\n"<<"第"<<sum<<"次排序结果: ";for(int i=1;i<=N-1;i++){cout<<s[i]<<" ";}}kjs[2]=1; //只有一个辅助空间s[0]cout<<"\n\n该方法的时间复杂度为："<<"O("<<sjs[2]<<"); 空间复杂度为："<<"O("<<kjs[2]<<")"<<endl;return 0;}int jdxz(int s[]) //简单选择排序的主要函数{ cout<<"\n您选择的是: [简单选择排序方法] \n"<<endl;cout<<"\n数据的初始顺序如下: "<<endl;int i;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;sjs[2]=kjs[2]=0;jdxzs(s);cout<<"\n排序后数据的顺序如下："<<endl;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;return 0;}//堆排序算法int jdd(int s[],int i,int n) //调整大根堆{ s[0]=s[i]; //倍份待筛结点元素值int j=2*i; //s[j]为s[i]的左孩子while(j<=n) //当s[i]的左孩子不为空时{if(j<n&&s[j]<s[j+1])j++; //j为i 结点较大孩子的下标if(s[0]>=s[j])break; //找到位置,终止循环sjs[3]++;s[i]=s[j];i=j;j=2*i;}s[i]=s[0];return 0;}int ddpxs(int s[],int n){ sum=0;int i;for(i=n/2;i>0;i--)jdd(s,i,n);for(i=n;i>1;i--){ s[0]=s[1];s[1]=s[i];s[i]=s[0];sjs[3]++;sum++;cout<<"\n第"<<sum<<"次排序后的结果：";for(int t=1;t<=N-1;t++){cout<<s[t]<<" ";}jdd(s,1,i-1);}kjs[3]=1; //只用了一个辅助存储空间s[0]cout<<"\n\n该方法的时间复杂度为："<<"O("<<sjs[3]<<"); 空间复杂度为："<<"O("<<kjs[3]<<")"<<endl;return 0;}int ddpx(int s[],int n){ cout<<"\n您选择的是: [堆排序方法] \n"<<endl;cout<<"\n数据的初始顺序如下: "<<endl;int i;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;sjs[3]=kjs[3]=0;ddpxs(s,N-1);cout<<"\n排序后数据的顺序如下："<<endl;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;return 0;}//冒泡排序算法int mppxs(int s[]){ sum=0;int i,j;for(i=1;i<N-1;i++){ for(j=N-1;j>=i;j--)if(s[j]<s[j-1]){ s[0]=s[j-1]; //s[0]作为交换时的暂存单元s[j-1]=s[j];s[j]=s[0];sjs[4]++;}sum++;cout<<"\n"<<"第"<<sum<<"排序后的结果是: ";for(int i=1;i<=N-1;i++){cout<<s[i]<<" ";}}kjs[4]=1; //只用了一个用于交换的暂存单元s[0]cout<<"\n\n该方法的时间复杂度为："<<"O("<<sjs[4]<<"); 空间复杂度为："<<"O("<<kjs[4]<<")"<<endl;return 0;}int mppx(int s[]) //冒泡排序的主要函数{ cout<<"\n您选择的是: [冒泡排序方法] \n"<<endl;cout<<"\n数据的初始顺序如下: "<<endl;int i;;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;sjs[4]=kjs[4]=0;mppxs(s);cout<<"\n排序后数据的顺序如下："<<endl;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;return 0;}//快速排序算法int huafens(int s[],int i,int j) //快速划分函数{s[0]=s[i]; //s[0]为辅存kjs[5]++;while(i<j){while(i<j&&s[j]>=s[0])j--;if(i<j){s[i]=s[j];i++;sjs[5]++;}while(i<j&&s[i]<=s[0])i++;if(i<j){s[j]=s[i];j--;sjs[5]++;}}s[i]=s[0];return i;}int kspxs(int s[],int low,int high){if(low<high){ int p;p=huafens(s,low,high);sum++;cout<<"\n"<<"第"<<sum<<"次划分的结果为: ";for(int j=1;j<=N-1;j++){cout<<s[j]<<" ";}kspxs(s,low,p-1);kspxs(s,p+1,high);}return 0;}int kspx(int s[],int low,int high){ cout<<"\n您选择的是: [快速排序方法] \n"<<endl;cout<<"\n数据的初始顺序如下: "<<endl;int i;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;sum=0; //排序次数清零sjs[5]=kjs[5]=0;kspxs(s,1,N-1);cout<<"\n\n该方法的时间复杂度为："<<"O("<<sjs[5]<<"); 空间复杂度为："<<"O("<<kjs[5]+1<<")"<<endl;cout<<"\n排序后数据的顺序如下："<<endl;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;return 0;}//2-路归并排序算法int gbzs(int s[],int sm[],int low,int m,int high)//核心操作，对相邻的两个子文件进行升排序{ int i,j,k;i=low;j=m+1;k=low; //初始化while(i<=m&&j<=high){if(s[i]<=s[j]){sm[k++]=s[i++];sjs[6]++;}else{sm[k++]=s[j++];sjs[6]++;}}while(i<=m){sm[k++]=s[i++];//将s[low,m]中剩余的部分复制到sm中sjs[6]++;}while(j<=high){sm[k++]=s[j++];//将s[m+1,high]中剩余的部分复制到sm中sjs[6]++;}return 0;}int gbycs(int s[],int sm[],int len,int n)//做一趟归并升排序{ int i;for(i=1;i+2*len-1<n;i=i+2*len)gbzs(s,sm,i,i+len-1,i+2*len-1);if(i+len-1<n)gbzs(s,sm,i,i+len-1,n);elsefor(int j=i;j<=n;j++)sm[j]=s[j];return 0;}int gbpxs(int s[],int sm[],int n) //升序{ int m=0;int len=1;while(len<n){gbycs(s,sm,len,n);sum++;cout<<"\n"<<"第"<<sum<<"次排序后的顺序显示：";for(int i=1;i<=10;i++){cout<<sm[i]<<" ";}len=len*2;gbycs(sm,s,len,n);}kjs[6]=N-1;cout<<"\n\n该方法的时间复杂度为："<<"O("<<sjs[6]<<"); 空间复杂度为："<<"O("<<kjs[6]<<")"<<endl;return 0;}int gbpx(int s[],int sm[],int n){ cout<<"\n您选择的是: [2-路归并排序方法] \n"<<endl;cout<<"\n数据的初始顺序如下: "<<endl;int i;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;sum=0;sjs[6]=kjs[6]=0;gbpxs(s,sm,N-1);cout<<"\n排序后数据的顺序如下："<<endl;for(i=1;i<=N-1;i++){cout<<s[i]<<" ";}cout<<endl;return 0;}。
