排序，，，

这个是排序
这个是开始的代码，但是有三个测试点超时，我觉得可能是这个时间复杂度太高了（虽然我并不能证明我这个想法）但是想想这个是没有优化前的算法，优化后的我还没看也还没想，

#include  
#include 
#define MAX 100006//数组要开大点，不然报错 REusing namespace std;int mid(int a[],int left,int right){int pivot=a[left];//定义一个点用来比较while(left<right){while(pivot<=a[right]&&left<right) right--;a[left]=a[right];//right的任务就是找出比pivot小的数据并交换while(pivot>=a[left]&&left<right) left++;a[right]=a[left];//left是找出比pivot大的数据并交换}a[left]=pivot;//更新pivotreturn left;
}void quicksort(int a[],int left,int right){if(left<=right){int sum=mid(a,left,right);quicksort(a,left,sum-1);//递归左半边quicksort(a,sum+1,right);//递归右半边}
}int main(){int f[MAX],n,i;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&f[i]);quicksort(f,0,n-1);for(i=0;i<n;i++){if(i==0)printf("%d",f[i]);elseprintf(" %d",f[i]);}cout<<endl;return 0;
}

现在再试试另一个
—————————————————————————————
看了优化后的算法之后我还是不太懂为什么上面一个会超时，这个是通过了的代码

#include  
#include 
#define MAX 100006using namespace std;void quicksort(int a[],int left,int right){int pivot=a[(left+right)/2];//取中间的数作为比较的数int i,j;i=left; j=right;while(i<=j){while(a[i]<pivot) i++;while(a[j]>pivot) j--; if(i<=j){swap(a[i],a[j]);i++;j--;}}if(left<j) quicksort(a,left,j);if(i<right) quicksort(a,i,right);
}int main(){int f[MAX],n,i;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&f[i]);quicksort(f,0,n-1);for(i=0;i<n;i++){if(i==0)printf("%d",f[i]);elseprintf(" %d",f[i]);}cout<<endl;return 0;
}

看见有评论说是因为开头的 pivot=a[(left+right)/2]

会比int a=a[(left+right)/2]; int povit=a;要快，我刚刚试了这个算法不超时主要原因不是这个，
emmmmmmmm看看视频吧，害，看视频都没有系统讲解的，每个人有每个人不一样的代码和思路，但总体来说优化的方向都差不多，在花点时间归纳一下他们的经验就应该不错了，毕竟要我自己有思路才好，但是学这个算法的时间为免有点太长了…看视频发现他们这个跟我上面那个优化后的算法不是优化的同一个地方，大部分是优化递归数量以减少算法运行时间，我这个我愣是想不通为啥它就能减少时间
救命我感觉我学不进去了，为什么想不动，真的是欲哭无泪啊。
我知道了，确实是第一个的时间复杂度太高了,但是我不知道第二个代码优化在哪，看不出

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！