真爱无限的知识驿站

code：

#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;
}

pkm@pkmlinux:~/files$ g++ sort1.cpp

pkm@pkmlinux:~/files$ a.out

用时：1.06

22 23 24 25 26 27 28 29 30 31 

用时：0.49

22 23 24 25 26 27 28 29 30 31 

用时：0.47

22 23 24 25 26 27 28 29 30 31 

用时：0

22 23 24 25 26 27 28 29 30 31