quick.cpp

用分治法对100个数进行排序

#include<iostream.h>
#include<stdio.h>
#define SIZE 100

void displayArray(int);
void qStore(int ,int );
int Partition(int p,int r);
void swap(int a,int b);

int a[SIZE];
void main()
{
	FILE *fp;
  	
	if((fp=fopen("data.dat","r"))!=NULL)
	{ for(int i=0;i<100;i++)
	   {
		fscanf(fp,"%d",&a[i]);
	}
	   cout<<endl;
	}
	else
	{
		cout<<"无法打开文件!\n";
	}
	cout<<"排序前的序列：\n";
	displayArray(SIZE);
    cout<<"排序后的序列:\n";
	qStore(0,SIZE-1);
    displayArray(SIZE);
	
}
//进行排序
void qStore(int p,int r)
{
	if(p<r)
	{
		int q=Partition(p,r);
        qStore(p,q-1);
		qStore(q+1,r);
	}
}
int Partition(int p,int r)
{
	int i=p,j=r+1;
	int x=a[p];
	while(true)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j) break;
		swap(i,j);
	}
   a[p]=a[j];
   a[j]=x;
   return j;
}

void swap(int i,int j)
{
	int tmp;
	tmp=a[i];		
	a[i]=a[j];
	a[j]=tmp;
}
//输出原始数组中的数据
void displayArray(int len)
{
  for(int i=0;i<len;i++)
  {
	  if(i!=len-1) 
	  {
		  cout<<a[i]<<"\t";
	  }
	  else
	  {
		  cout<<a[i]<<endl;
	  }
  }
}