quicksort.cpp

快速排序算法

/*快速排序的C++语言描述*/
#include<iostream.h>
#include<stdlib.h>
#include<windows.h>

#define N 10000

template<class T>void QuickSort(T a[],int p,int r);
template<class T>int Partition(T a[],int p,int r);

void main()
{
	int const ARRAYLG(1000);//数组长度
	int a[ARRAYLG];
	for(int i=0;i<ARRAYLG;i++)//给数组赋值
	{
		a[i]=rand()%N;
	}
	LARGE_INTEGER litmp;
	LONGLONG QPart1,QPart2;
	double dfMinus,dfFreq,dfTim;
	QueryPerformanceFrequency(&litmp);
	dfFreq=(double)litmp.QuadPart;//获得计数器的时钟频率
	QueryPerformanceCounter(&litmp);
	QPart1=litmp.QuadPart;//获得初始值

	QuickSort(a,0,ARRAYLG-1);//排序

	QueryPerformanceCounter(&litmp);
	QPart2=litmp.QuadPart;//获得中止值
	dfMinus=(double)(QPart2-QPart1);
	dfTim=dfMinus/dfFreq;//获得对应的时间值，单位为秒
	cout<<"The total time is:"<<dfTim<<" seconds."<<endl;
}

template<class T>
void QuickSort(T a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}

template<class T>
int Partition(T a[],int p,int r)
{
	int i=p,j=r+1;
	T x=a[p];
	while(true)
	{
		while(a[++i]<x)
			;
		while(a[--j]>x)
			;
		if(i>=j)
			break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
template<class T>
inline void Swap(T &s,T &t)
{
	T temp=s;
	s=t;
	t=temp;
}