算法的时间复杂度 实验报告

} }

//一次快速排序

int Partition(int arr[],int left,int right ) {

int i=left; //作为划分中的枢纽值 int j=right; //右边界

int temp=0; //交换时的临时变量 do{

do i++; //扫描左侧，当当前位置值大于枢纽值时停止 while (arr[i]

do j--; //扫描右侧，当当前位置值大于枢纽值时停止 while (arr[j]>arr[left]); if(i

temp=arr[i]; //交换当前i和j记录位置的值 arr[i]=arr[j]; arr[j]=temp; } }

while(i

temp=arr[left]; //i>j时本趟循环结束，交换枢纽值和j位置的值 arr[left]=arr[j]; arr[j]=temp; return j; }

//归并排序合并两有序的子序列

void Union(int arr[],int left,int mid,int right) {

int temp[10000]; //临时使用的辅助数组 int i=left; int j=mid+1; int k=0;

while((i<=mid)&&(j<=right)){ //比较后把i，j中最小的放入temp中 if(arr[i]<=arr[j])

temp[k++]=arr[i++]; else temp[k++]=arr[j++]; }

while(i<=mid)

temp[k++]=arr[i++]; while(j<=right)

temp[k++]=arr[j++]; for(i=0,k=left;k<=right; )

arr[k++]=temp[i++]; //把排好序临时数组放回原数组 }

六、 实验结果

1.数组大小ARRAY_MAXSIZE为10000如下：

2.数组大小ARRAY_MAXSIZE为8000如下

3.数组大小ARRAY_MAXSIZE为5000如下：

七、 实验分析

1、各算法时间时间消耗图

2、各算法时间性能分析表：

方法 起泡排序 快速排序 选择排序 归并排序 最好情况 O(n) O(nlog2n) O(n２) O(nlog2n) 最坏情况 O(n２) O(n２) O(n２) O(nlog2n) 平均情况 O(n２) O(nlog2n) O(n２) O(nlog2n) 3、分析与说明：

由算法时间复杂度表分析，起泡排序在最好情况下时间性能好，最坏情况和平均情况和选择排序一样，选择排序的时间性能都不高，均为O(n２)，根据平均情况来看，快速排序和归并排序的时间性能一样，且最坏情况时归并排序优于快速排序。

对于随机数组序列，数组大小为10000，8000，5000时候，归并排序算法执行时间和快速排序时间都相对较短，简单选择排序缓慢，而起泡排序则是最耗时的。但是当数组由10000变到5000时，归并排序的时间性能变化不大，而快速排序时间性能提高很多，起泡排序时间性能下降慢，所以起泡排序在随机序列中的性能不高。 对于非递减数组序列，起泡排序时间消耗为均为0（0不代表没耗时，只是CPU处理速度太快，没法显示更精确的时间），而其他的快速排序，选择排序，归并排序和随机数组序列情况接近。所以起泡排序在非递减序列中的时间性能高。