算法分析作业1_简单排序算法分析

1、排序算法复杂性分析一秦健刘鹏刘明欢我们郑重承诺，本作业的内容均为原创，没有任何抄袭他人成果的行为，也不存在他人代写作业和程序的行为。引用他人成果或公开资料的部分都已经按照正确的格式在参考文献中标出。作者签字得分统计学生填写老师填写姓名学号工作所占比例得分分别得分秦健2013140134%刘鹏2013140033%刘明欢2013071133%摘要本文通过三种简单排序-插入、冒泡和选择排序算法并运用C+语言编程实现，以计算简单排序算法复杂度。首先，利用不同规模下随机产生的不同序列，计算三种排序方法下的元运算-比较、交换、移动的次数来定量刻画排序算法的时间复杂度，即序列规模与元运算次数的关系，得到三

2、种算法的时间复杂度均为n2，这说明这三种排序算法具有相同时间复杂度，并且实现简单，所以也归为一类简单排序算法。其次，采用统一规模下的不同排列顺序，主要是两个极端序-顺序、逆序的情况下分析三种算法的时间复杂度，得到算法的最好时间复杂度为1，最坏时间复杂度为n2，反映出不同顺序的序列导致的排序算法时间复杂度的巨大差异性，并且插入、冒泡排序与选择排序之间的优劣也逐渐显现出来，主要是由于逆序对的数目导致交换次数变化的缘故。最后，本文将作为其他排序算法的时间复杂度作为后续扩展部分，以待完善。本文将围绕以下两个问题进行讨论分析:1） 设计一个程序，程序的输入为n个（n必须要从键盘输入）0到10000的正整

3、数（正整数可以是随机产生），输出为对这n个数进行从小到大排序后的序列。排序方法分别使用插入排序、冒泡排序和选择排序。2） 以两个数比较、两个数交换、移动一个数为基本计算单位，测试你所编写的程序对于n=100,500,1000,2000四种输入规模的时间复杂度。一、算法复杂度1.1算法复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。  计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时

4、间复杂性和空间复杂性之分。1.2时间复杂度【1】如果分别用N,I和A表示算法要解的问题的规模、算法的输入和算法本身，而且用C表示复杂性，把时间复杂性和空间复杂性分别用T和S来表示那么有 C=FN,I,A T=TN,I,A -(1)S=SN,I,A设计算机所提供的元运算有k种，分别记为1,2,k。又设每执行一次这些元运算所需要的时间分别为t1,t2,tk。经统计用到的元运算i的次数为ei,i=1,2,k，则有ei=eiN,I。因此，TN,I=i=1ktieiN,I。记最坏情况、最好情况和平均情况下的时间复杂性，并分别有 TmaxN=maxIDNTN,I=maxIDNi=1ktieiN,I=TN,

5、I*TminN=minIDNTN,I=minIDNi=1ktieiN,I=TN,I TavgN=i=1kP(I)TN,I=i=1kP(I)i=1ktieiN,I其中，DN是规模为N的合法输入的集合；I*, I分别是DN中使TN,I*达到TmaxN的合法输入与使TN,I达到TminN的合法输入；而P(I)是在算法的应用中出现输入I的概率。二、简单排序算法2.1简单排序法思想【2】2.1.1插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据

6、中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。2.1.2冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序是这样实现的：首先从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交

7、换。然后重复1号步骤，直至再也不能交换。2.1.3选择排序选择排序工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：初始状态：无序区为R1.n，有序区为空。第1趟排序在无序区R1.n中选出关键字最小的记录Rk，将它与无序区的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。2.2简单排序法流程图此处仅给出选择排序算法流程图，冒泡、插入排序算法流程图可根据2.1算法步骤类似给出。2.3简单排序法伪代码同理,此

8、处仅给出插入排序算法伪代码，冒泡、选择排序算法伪代码可根据附录中的程序类似给出。INSERTION-SORT(A)Begin1 forj=0 to lengthA-12 if Aj>Aj+1 then key=Aj3 /InsertAj+1 into the sorted sequence A0.j.4 i=j+15 while i>0 and Ai <key6 Ai+1->key 7 Ai ->Ai+18 i=i-19 print AiEnd 三、算法实现与分析3.1时间复杂度-规模分析利用C+面对对象编程语言在VC+6.0编译环境下进行三种简单排序算法的编程实

9、现，关键代码详见附录，程序结果截图详见附录，整理结果如下表1所示:排序算法序列规模交换次数比较次数元运算次数插入排序100245525495004500665846707713366110002513452523365036812000100917410111682020342冒泡排序1002455494974045006658412468419126810002513454884727508172000100917419987003007874选择排序10093495050435004921247501252421000995499500500495200019871990002000987

10、表1简单排序算法时间复杂度从表1可以看出随着排序序列规模的增加，插入排序和冒泡排序算法元运算次数较选择排序算法运算次数增加愈加明显，这主要是由于交换次数所造成的，本质上是由于插入和排序的交换为相邻交换，可能会增加逆序对的数目，导致下一次循环交换次数增多，而选择排序的交换为最值交换，从表1也可以看出选择排序算法的交换次数和序列规模基本一致，这是因为每次循环最值只有一个，交换一次就减少一个。并且从表1可以看出插入和冒泡排序的交换次数是一样的，说明插入排序的移位操作本质上就是相邻交换，只不过交换顺序为冒泡交换的逆过程。此外，冒泡排序的比较次数明显高于插入排序和选择排序这是因为冒泡排序每次循环仅仅减少

11、一次比较运算，直到序列全部顺序。但是上表却不能明显显示出三种排序算法的时间复杂度和序列规模的关系，所以利用Excel数据作图1: 图1 简单排序算法复杂度折线从图中可以看出三种简单的排序算法的时间复杂度的曲线增长趋势基本一致，基本处于线性和平方项之间，进一步分析程序算法，从两层循环遍历可以得出三种简单排序算法的时间复杂度为n2，这与图1显示的结果基本吻合。3.2时间复杂度-排列分析由于初始序列的随机性难免使得部分结果出现偏差，就统一规模而言，选择两种固定的初始排列-顺序、逆序排列，考虑极端序下三种排序算法的时间复杂度，如下图2、图3所示:图2 顺序初始排序自然可以想到顺序排序的序列不需要任何交

12、换，但是需要一次遍历确定顺序排序，所以比较次数即为一次循环的次数，相比之下，选择排序却需要每次遍历重复确定每个最值，所以导致比较次数十分巨大，由此可知当原始序列接近于顺序或逆序对数较少时，采用插入和冒泡排序优于选择排序。由于没有逆序对的产生所以插入、冒泡排序算法的时间复杂度为1，即最好时间复杂度，而选择排序的时间复杂度却仍然为n2，这是由于庞大的比较次数所造成的。图3逆序排序同理，另一个极端即逆序，此时逆序对的数目是最大的，插入和冒泡排序算法的交换次数和比较次数相接近，但是选择排序优于最值的数目不变，所以交换次数大大降低，而且逆序条件下最值分布的对称性进一步减少了选择排序算法的交换次数。由此可

13、知当原始序列接近于逆序或逆序对数较多时，采用插入和冒泡排序优于选择排序。此时，三种排序算法的时间复杂度均为n2，即最坏时间复杂度，而选择排序的时间由于交换次数的较少，在常数项倍数下优于其余两种排序算法，但是比较次数的影响仍然使得算法并未得到量级上的优化。四、延展推广本文将作为其他排序算法-快速排序、希尔排序、堆排序、技术排序的时间复杂度作为后续扩展部分，其他排序算法在交换次数和比较次数上的优势将明显体现出来，通过数据结构分析可以分析出其时间复杂度为nlogn，但是运算优化也将使得算法复杂的代价，使得编程较难编写，难于维护。五、参考文献1王晓东.算法设计与分析M.北京:清华大学出版社.2014(

14、2015.10重印)2 附录简单排序结果截图简单排序元计算截图100规模500规模1000规模2000规模简单排序C+程序关键代码void Sort:Insert_Sort()/插入排序算法cout<<"*"cout<<"insert sort data:"<<endl;Clear();/Display();int i,j;for (i=0;i<n-1;i+)if (newdatai>newdatai+1)j=i+1;while (j!=0)if (newdataj>=newdataj-1)compa

15、retimes+;break;swap(newdataj,newdataj-1);swaptimes+;comparetimes+;j-;/Display();elsecomparetimes+;Display(1);void Sort:Bubble_Sort()/冒泡排序算法cout<<"*"cout<<"bubble sort data:"<<endl;Clear();/Display();int i,j;int beforeswap=-1; for (i=n-1;i>0;i-) if (beforeswap

16、=swaptimes)break;elsebeforeswap=swaptimes;for (j=n-1;j>n-i-1;j-)if (newdataj-1>newdataj)swap(newdataj-1,newdataj);swaptimes+;comparetimes+;/Display();elsecomparetimes+; Display(1);void Sort:Comparison_Sort()/选择排序算法cout<<"*"cout<<"comparison sort data:"<<endl;Clear();/Display();int i,j,k;int minnum;for (i=0;i<n;i+)k=i;minnum=newdatai;for (j=i+1;j<n;j+)if (newdataj<minnum)k=j;min