发布时间 : 星期六 文章算法的时间复杂度 实验报告更新完毕开始阅读87a00bdf50e2524de5187ec1
} }
//一次快速排序
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处理速度太快，没法显示更精确的时间），而其他的快速排序，选择排序，归并排序和随机数组序列情况接近。所以起泡排序在非递减序列中的时间性能高。