linux下练习 c++ 几种排序算法
#include <iostream>#include<algorithm>#include<ctime>using namespace std;void sort(int* a,int n)//普通冒泡排序{bool changed;do{changed=false;for(int i=1;i<n;i++){if(a[i]<a[i-1]){swap(a[i],a[i-1]);changed=true;}}--n;}while(changed);}void sort1(int* a,int n)//插入排序{int j;for(int i=1;i<n;i++){int t=a[i];for(j=i;j>0&&t<a[j-1];j--)a[j]=a[j-1];a[j]=t;}}void sort2(int* a,int n)//高效冒泡排序{int j;for(int i=0;i<n-1;i++){int t=i;for(j=i+1;j<n;j++)if(a[j]<a[t]) t=j;if(i!=t) swap(a[t],a[i]);}}void sort3(int* a,int n)//快速（分组）排序{if(n<=1) return;else if(n==2){if(a[0]<=a[1]) return;else swap(a[0],a[1]);}else{swap(a[n/2],a[0]);int jie =a[0];int* L=a+1;int* R=a+n-1;while(L<R){while(L<R && *L<jie) ++L;while(a<R && *R>=jie) --R;if(L<R) swap(*L,*R);}if(*R <jie) swap(*R,a[0]);sort(a,R-a);sort(R+1,n-1-(R-a));}}int main(){const int N=10240;int a[N];for(int i=0;i<N;i++){a[i]=N-i;}clock_t t1=clock();sort(a,N);clock_t t2=clock();cout<<"用时："<<double(t2-t1)/CLOCKS_PER_SEC<<endl;for(int i=21;i<31;i++){cout<<a[i]<<' ';}cout<<endl;//int b[5]={45,42,67,88,11};for(int i=0;i<N;i++)//重新赋值{a[i]=N-i;}t1=clock();sort1(a,N);t2=clock();cout<<"用时："<<double(t2-t1)/CLOCKS_PER_SEC<<endl;for(int i=21;i<31;i++){cout<<a[i]<<' ';}cout<<endl;for(int i=0;i<N;i++)//重新赋值{a[i]=N-i;}t1=clock();sort2(a,N);t2=clock();cout<<"用时："<<double(t2-t1)/CLOCKS_PER_SEC<<endl;for(int i=21;i<31;i++){cout<<a[i]<<' ';}cout<<endl;for(int i=0;i<N;i++)//重新赋值{a[i]=N-i;}t1=clock();sort3(a,N);t2=clock();cout<<"用时："<<double(t2-t1)/CLOCKS_PER_SEC<<endl;for(int i=21;i<31;i++){cout<<a[i]<<' ';}cout<<endl;}