kuaipai.cpp

快速排序 不是稳定的快速排序 优化了的原位快速排序

#include"stdio.h"
#include"iostream"
#include"stdlib.h"
using namespace std;
int shuzu[10000];
void putong(int start,int end)
{
	int i,j;
	int temp;
	for(i=end;i>start;i--)
		for(j=start;j<i;j++)
		{
			if(shuzu[j]>shuzu[j+1])
			{
				temp=shuzu[j];
				shuzu[j]=shuzu[j+1];
				shuzu[j+1]=temp;
			}
		}
}
int kuai(int start,int end)
{
	int mid,k,i,j;
	int temp;
	mid=(start+end)/2;
	if(shuzu[mid]>=shuzu[start]&&shuzu[start]>=shuzu[end]||shuzu[end]>=shuzu[start]&&shuzu[start]>=shuzu[mid])
	   k=start;
	else
	   if(shuzu[mid]>=shuzu[end]&&shuzu[end]>=shuzu[start]||shuzu[start]>=shuzu[end]&&shuzu[end]>=shuzu[mid])
          k=end;
	   else
		   k=mid;
	temp=shuzu[k];
	shuzu[k]=shuzu[end];
	i=start;
	j=end;
	while(i!=j)
	{
		while(i!=j&&shuzu[i]<=temp)
		   i++;
		if(i!=j)
		{
			shuzu[j]=shuzu[i];
			j--;
		}
		while(i!=j&&shuzu[j]>=temp)
		    j--;
		if(i!=j)
		{
			shuzu[i]=shuzu[j];
			i++;
		}
	}
	shuzu[i]=temp;
	return i;
}
void pai(int start,int end)
{
   int num;
   int mid;
   num=end-start;
   if(num<10)
	   putong(start,end);
   else
   {
	   mid=kuai(start,end);
	   pai(start,mid-1);
	   pai(mid+1,end);
   }
}
void dayin(int geshu)
{
    int i;
	for(i=0;i<geshu;i++)
	   cout<<shuzu[i]<<"    ";
}
int main()
{
	freopen("a.txt","r",stdin);
	freopen("b.txt","w",stdout);
	int num;
	int geshu=0;
	while(scanf("%d",&num)!=EOF)
	{

		shuzu[geshu]=num;
		geshu++;
	}
	pai(0,geshu-1);
	dayin(geshu);
	return 0;
}