#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