四种排序算法时间测试.cpp

四种排序算法quicksort

#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <iomanip.h>
#include <math.h>

//划分算法
int SPLIT(int x[],int low,int high)
{
	int i = low, j = high; 
	int temp;
	while (i<j)
    {	
		while(i<j && x[i]<=x[j]) j--;                //从右侧扫描
		if(i<j)
		{
			temp = x[i]; x[i] = x[j]; x[j] = temp;   //将较小的数交换到前面
		    i++;
		}
		while(i<j && x[i]<=x[j]) i++;                //从左侧扫描
		if(i<j)
		{
			temp = x[i]; x[i] = x[j]; x[j] = temp;   //将较大的数交换到后面
			j--;
		}
	}
	return i;                                        //i为分界数值的最终位置
}

//快速排序***********************************************************
void QUICKSORT(int x[],int low,int high)
{
	int w;
	if(low<high)                  //递归结束
	{ 
		w = SPLIT(x,low,high);    //一次划分
		QUICKSORT(x,low,w - 1);   //递归地对左侧子序列进行快速排序
		QUICKSORT(x,w + 1,high);  //递归地对右侧自序列进行快速排序
	}
}

//向下筛选
void SIFT_DOWN(int x[],int k,int m)
{
	int temp;
	int i=k, j=2*(i+1)-1;                 //置i为要筛的结点，j为i的左孩子
	while(j<=m)                           //筛选还没进行到叶子结点
	{
		if(j<m && x[j]<x[j+1]) j++;       //比较i的左右孩子，j为较大者
		if(x[i]>x[j]) break;              //根结点已经大于左右孩子中的较大者
		else
		{
			temp = x[i]; x[i] = x[j]; x[j] = temp;          //将根结点与子结点j交换
			i = j; j = 2*(i+1)-1;                           //被筛结点位于原来结点j的位置
		}
	}
}
			
//堆排序***********************************************************
void HEAPSORT(int x[],int n)
{
	int temp;
	for(int i = (n-1)/2; i>=0; i--)         //创建堆，从最后一个非终结点至根结点
		SIFT_DOWN(x,i,n);
	for(i = 0; i<=n; i++)                   //重复执行移走堆顶及重复建堆的操作
	{
		temp = x[0]; x[0] = x[n-i]; x[n-i] = temp;
		SIFT_DOWN(x,0,n-i-1);
	}
}


//基数排序***********************************************************
struct list
{
	int e[50000];
	int *f, *r;
};

void RADIXSORT(int x[],int n)
{
	list *l = new list[10];                //定义10个list类型空数组
	for(int j = 0; j<10; j++)
	{
		l[j].f = l[j].r = &l[j].e[0];      //初始化10个数组的头尾指针
	}
	for(int k = 1; k<=5; k++)
    {
	    for(int i = 0; i<=n; i++)
		{
		    int m = (int)(x[i]%(int)(pow(10,k))/pow(10,k-1));  //取出序列中每个数对应位的数值
			*(l[m].r) = x[i];              //将初始序列按序列中每个数对应位的数值分类，并放到相应的list类型数组中尾指针所指位置
			l[m].r++;                      //尾指针移到数组的下一位置
		}
		int z = 0;
		for(int a = 0; a<10; a++)
		{
			int *p = l[a].f;
			while(p!=l[a].r)               //头尾指针所指位置相同时，说明list类型数组的数已被取完
			{
				x[z++] = *(p++);           //将10个list类型数组的数覆盖到原输入序列数组中
			}
			l[a].r = l[a].f;               //每次取完一个list类型数组，将尾指针指回头指针所指位置
		}
	}
	delete []l;
}


//合并
void MERGE(int x[],int l,int m,int h)
{
	int *B = new int [h-l+1];
	int i = l,j = m+1,k = 0;
	while(i<=m && j<=h)
	{
		if(x[i]<=x[j]) B[k++] = x[i++];      //取r[i]和r[j]中的较小者放入B[k]
		else B[k++] = x[j++];
	}
	if(i<=m) while(i<=m)                     //若第二个子序列处理完，则将第一个子序列剩余数直接放进B中
		        B[k++] = x[i++];
	else while(j<=h)                         //若第一个子序列处理完，则将第二个子序列剩余数直接放进B中
		    B[k++] = x[j++];
	for(k = 0; k<(h-l+1); k++)
		x[l+k] = B[k];
	delete []B;
}

//合并排序***********************************************************
void MERGESORT(int x[],int low,int high)
{
	if (low < high)
	{
		int mid = (low+high)/2;
		MERGESORT(x,low,mid);
		MERGESORT(x,mid+1,high);
		MERGE(x,low,mid,high);
	}
}



/////////////////////////////////////////////////////*********************************************************
/////////////////////////////////////////////////////*******************************powered by kui************
void main()
{
	int ch;
	clock_t t1,t2;
	double t,sum = 0.0,avg;
	loop:
	cout<<"\n※请选择所需测试的排序算法※\n";
	cout<<"  1.快速排序\n";
	cout<<"  2.堆排序\n";
	cout<<"  3.基数排序\n";
	cout<<"  4.合并排序\n";
	cout<<"->请选择：";
	cin>>ch;
	int c;
	int cc;
	int f = 0;
	cout<<"\n请选择输入的待排序列类型：\n";
	cout<<"1.随机排列\n";
	cout<<"2.升序排列\n";
	cout<<"3.降序排列\n";
	cout<<"请选择：";
	cin>>cc;
	for(int i = 0; i<4; i++)
	{
		cout<<"\n请输入待排序序列长度值：";
	    cin>>c;
		switch(cc)                             //选择输入的序列类型
		{
			case 1:
				f=1;
				break;
			case 2:
				f=2;
				break;
			case 3:
				f=3;
				break;
			default:
				cout<<"输入错误，请重新输入!\n";
		}
		for(int j = 0; j<10; j++)
		{
			int *A = new int[c];               //动态分配整型数组
			int *C = new int[c];
			if(f==1)                           //生成随机排序序列
			{
				for(int k=0; k<c; k++)
				{
					A[k] = rand();
				}
			}
			if(f==2)                           //生成升序排序序列
			{
				for(int k=0; k<c; k++)
					{
						A[k] = rand();
					}
					QUICKSORT(A,0,c - 1);
			}
			if(f==3)                           //生成降序排序序列
            {
				for(int k=0; k<c; k++)
				{
					C[k] = rand();
				}
				QUICKSORT(C,0,c - 1);
				int b = 0;
				for(k =c-1; k>=0; k--)
				{
					A[b++] = C[k];
				}
			}
            t1 = clock();                      //开始计时
			switch(ch)
			{
				case 1:
					QUICKSORT(A,0,c - 1);
					break;
				case 2:
					HEAPSORT(A,c-1); 
					break;
				case 3:
					RADIXSORT(A,c-1);
					break;
				case 4:
					MERGESORT(A,0,c-1);
					break;
				default:
					cout<<"输入错误，请重新输入!\n";
			}
			t2 = clock();                      //结束计时
			t = (double)(t2 - t1)/CLOCKS_PER_SEC;
			sum=+t;
			delete []A;                        //释放数组
			delete []C;
		}
		avg = sum/10.0;                        //平均时间
		cout<<"\n******************************************************\n";
		cout<<"每组序列长度为"<<c<<"，测试10组序列，平均耗时为"<<avg<<"s"<<endl;
		cout<<"******************************************************\n";
	}
	goto loop;
}