《实验,顺序算法,心得体会》由会员分享，可在线阅读，更多相关《实验,顺序算法,心得体会（8页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划实验,顺序算法,心得体会计算机算法设计与分析实验报告学号：XX姓名：吕功建班级：实验一快速排序一、实验目的1）以排序问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现；3）熟练掌握快速排序算法的实现；4)理解常见的算法经验分析方法；二、算法思想基本描述分治算法思想：把规模为n的问题分成k个规模较小的子问题，且每个子问题相互独立且于原问题性质相同，递归的求解子问题，最后合并得到原问题的解。插入算法思想：在无序的数组中，先将序列中的第一个数字看作是有序子序列，然后从第
2、二个记录起逐个进行插入，直至将整个序列变成有序序列为止。快速排序算法思想：快速算法是一种基于分治技术的重要排序算法，把对n个对象的排序看作是对1到n的n个整数的排序。快速排序算法的基本思想是从中取一适合的关键字k，以k为标准把需要排序的n个对象分成两部分，一部分比k小，另一部分比k大，即：(小于k的部分)k然后对两部分分别进行快速排序，排序完毕后，简单的合并连接起来即可，算法还可递归的进行。三、算法流程图插入排序：四、算法执行结果及分析1、生成的随机数：2、运行时间插入排序：快速排序：3、排序结果：结论：从上图中结果可见，完成XX个相同随机数的排序，插入排序的时间为5ms，而快速排序只用了1m
3、s，之间相差4ms，而且当排序的数量增加时，快速排序用时要远远少于插入排序，由此可见，快速排序比插入排序更优。五、实验的心得体会、经验快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(nn)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。附：算法实现代码：因为随机数的生成是在中，所以需要先运行此程序。插入排序代码：packagesort;import;import;i
4、mport;实验课程：算法分析与设计实验名称：几种排序算法的平均性能比较实验目标：几种排序算法在平均情况下哪一个更快。加深对时间复杂度概念的理解。实验任务：实现几种排序算法。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A(low+high)/2)中其值居中者。随机产生20组数据。数据均属于范围内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间。根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境：PC；C/C+等编程语言。实验主要步骤：(1)明确实验目标和具体任务；(2)理解实验所涉及的几个分类算法；(3)编写
5、程序实现上述分类算法；(4)设计实验数据并运行程序、记录运行的结果；(5)根据实验数据及其结果得出结论；(6)实验后的心得体会。一:问题分析：1:随机生成n个0到的随机数用来排序的算法如下.for(intn=1000;n=0&biaj)count+;ccp=aj;cp+;elsebreak;ccp=ai;cp+;/若j的值还小于fi则继续把j到fi的值复制给c.此处也与书上的不同,主要由自己的理解来实现for(;jlow)count=count+spilt(a,low,w-1);序,例如只剩下一个数字时就不必再用spilt来排序了.if(w+1算法分析与设计实验报告学院专业班级任课教师学号姓名
6、实验日期：:XXXX:XXXX:：:实验一实验题目：排序问题求解实验目的：1）以排序问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现；3）熟练掌握快速排序算法的实现；4)理解常见的算法经验分析方法；实验环境计算机、C语言程序设计环境算法的基本思想描述：1.直接插入排序算法思想：假设待排序的n个记录R0，R1，Rn顺序存放在数组中，直接插入法在插入记录Ri(i=1，2，n-1)时，记录被划分为两个区间R0,Ri-1和Ri+1,Rn-1,其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，K0依次比较，找出应该插入的位置，将记录Ri插
7、，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。2.快速排序算法思想：快速排序是基于分治模式的。假设待排序数组Ap.r。分解：数组Ap.r被划分成两个子数组Ap.q-1和Aq+1.r,使得Ap.q-1中的每个元素都小于等于A(q)，而且，小于等于Aq+1.r中的元素。小标q也在这个划分过程中进行计算。解决：通过递归调用快速排序，对子数组Ap.q-1和Aq+1.r排序。合并：因为两个子数组是就地排序的，将它们合并
8、不需要操作：整个数组Ap.r已排序。算法理论分析：直接插入排序：快速排序(InsertionSort)过程中，对j=2,3,n,n=lengthA，设tj为while循环所做的测试次数。当for或while循环以通常方式退出时，测试要比循环体多执行1次。该算法总的运行时间是每一条语句执行时间总和。如果执行一条语句需要Ci步，又共执行了n次这条语句，那么它在总运行时间中占Cin。为计算总运行时间Tn，对每一对cost与times之积求和，得：在InsertionSort中，如果输入数组已经是排好序的话，就会出现最佳情况。对j=2,3,n中的每一个值，当j取其初始值j-1时，都有Ajitem。于是
9、，对j=2,3,n，有tj=1，最佳运行时间为：这一运行时间可以表示为，常量a和b依赖于语句的代价ci；因此它是n的一个线性函数。如果输入数组是按照逆序排序的，那么就会出项最坏的情况。我们必须将每个元素Aj与整个已排序的子数组A1.j-1中的每一个元素进行比较，因而，对j=2,3,n，有tj=j。在最坏情况下，InsertionSort的运行时间为：这一最坏情况运行时间可以表示为，常量a、b和c依赖于语句的代价Ci；因此这是一个关于n的二次函数。因此直接插入排序算法，在最佳情况下的时间复杂度是O(n)，在最坏情况下的时间复杂度为O()。快速排序：假设T(n)为对n个记录A1.n进行快速排序所需
10、时间，则由算法QuickSort可见：T(n)=Tpass(n)+T(k-1)+T(n-k)其中，Tpass(n)为对n个记录进行一趟快速排序Partition所需的时间，从一趟快速排序算法可见，其和记录数n成正比，可以用cn表示；T(k-1)和T分别为对A1.k-1和Ak+1.n中记录进行快速排序QuickSort和QuickSort所需时间。假设待排序列中记录是随机排列的，则在一趟排序之后，k取1至n之间任何一值的概率相同，快速排序所需时间的平均值则为假定Tavg(1)b(b为某个常量)，则快速排序的平均时间为Tavg(n)=knInn，其中n为待排序序列中记录的个数，k为某个常数。通常，快速排序被认为是，在所有同数量级的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)程序流程图：1.直接插入排序2.一趟快速排序流程图实验程序：实验结果：:实验分析：由下图可以明显的看出快速排序的效率远远高于直接插入排序，与理论分析相符。目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。
