[计算机]算法时间复杂度分析

《[计算机]算法时间复杂度分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、冒泡排序算法：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二

2、大的数）。如此下去，重复以上过程，直至最终完成排序。voidbubble_sort(int*x,intn)　　{　　intj,k,h,t;　　for(h=n-1;h>0;h=k)/*循环到没有比较范围*/　　{　　for(j=0,k=0;j*(x+j+1))/*大的放在后面，小的放到前面*/　　{　　t=*(x+j);　　*(x+j)=*(x+j+1);　　*(x+j+1)=t;/*完成交换*/　　k=j;/*保存最后下沉的位置。

3、这样k后面的都是排序排好了的。*/　　}　　}　　}　　}时间复杂性的分析：比较的时间耗费＋移动的时间耗费若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，考虑最坏情况，若记录序列的初始状态为"逆序"，则有第一次进行n-1次比较，n-1次移动第二次进行n-2次比较，n-2次移动第三次进行n-3次比较，n-3次移动。。。。第n-1次进行1次比较，1次移动共需进行1+2+3+。。。+n-1=n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度

4、为O(n*n)。堆排序算法：堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。调整堆算法：1234567H······························h··················　①初始化操作：构造为初始堆；　②每一趟排序的基本操作：1最大堆堆顶V[0]具有最大的排序码,将V[0]与V[n-1]对调,把具有最大排序码的对象交换到最后2再对前面的n-1个对象,调整堆,具有次最大排序码的对象又上浮到V[0]位置。3再对

5、调V[0]和V[n-2]堆排序对应程序代码：//array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度　　voidHeapAdjust(intarray[],inti,intnLength)//本函数功能是：根据数组array构建大根堆　　{　　intnChild;　　intnTemp;　　for(nTemp=array[i];2*i+1

6、f(nChildarray[nChild])　　++nChild;　　//如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点　　if(nTemp

7、ntarray[],intlength)　　{　　//调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素　　for(inti=length/2-1;i>=0;--i)　　{　　HeapAdjust(array,i,length);　　}　　//从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素　　for(inti=length-1;i>0;--i)　　{　　//把第一个元素和当前的最后一个元素交换,　　//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的　　Swap(&ar

8、ray[0],&array);　　//不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值　　HeapAdjust(array,0,i);　　}　　}时间复杂性的分析：建堆的时间耗费＋排序的时间耗费排序的时间耗费：结点个数高度比较次数j=2log2+1<=2×log2j=3log3+1<=2×log3j=4log4+1<=2×log4。。。。j=n-