算法的时间复杂度(2)

ndex]){ index=j; } } if(index!=i){ temp=arr[i]; arr[i]=arr[index]; arr[index]=temp; }?}}//一次快速排序intPartition(intarr[],intleft,intright){?inti=left;?intj=right;?inttemp=0;?do{ doi++; while(arr[i]<arr[left]); doj--; while(arr[j]>arr[left]); if(i<j){ temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; }?}?while(i<j);?temp=arr[left];?arr[left]=arr[j];?arr[j]=temp;?returnj;}实验结果1.数组大小为1000数组大小为2000数组大小为5000数组大小为10000实验分析1、性能分析表方法最好情况最坏情况平均情况起泡排序O(n)O(n2)O(n2)快速排序O(nlog2n)O(n2)O(nlog2n)选择排序O(n2)O(n2)O(n2)2、分析与说明:由算法时间复杂度表分析,起泡排序在最好情况下时间性能好,最坏情况和平均情况和选择排序一样,选择排序的时间性能都不高,均为O(n2)。对于随机数组序列,数组大小为10000,5000,2000,1000时候,快速排序时间都相对较短,简单选择排序缓慢,而起泡排序则是最耗时的。但是当数组由10000变到5000时,快速排序时间性能提高很多,起泡排序时间性能下降慢,所以起泡排序在随机序列中的性能不高。对于非递减数组序列,起泡排序时间消耗为均为0(0不代表没耗时,只是CPU处理速度太快,没法显示更精确的时间),而其他的快速排序,选择排序,和随机数组序列情况接近。所以起泡排序在非递减序列中的时间性能高。