排序综合.cpp

有很多数据结构的课设

// 排序综合.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#define size 15000

void quicksort(int R[], int left,int right);
void heapsort(int R[],int n);   //堆排序
void shellsort(int R[],int n);  //希尔排序

int a[size];

int _tmain(int argc, _TCHAR* argv[])
{
	system("color 3e");                            //利用DOS命令设定背景，文字颜色
	cout<<endl;
A:
	cout<<"欢迎使用本系统"<<endl;
	cout<<endl<<"****************************************************************************"<<endl;
	cout<<endl<<"请选择你要进行的操作："<<endl;
	cout<<endl<<"1，起泡法排序     2，堆排序    3，希尔排序    4，快速排序    5，退出系统"<<endl;
	int opinion;
	cin>>opinion;
	if(opinion==1)
	{
		for(int i=0;i<size;i++)
			a[i]=rand();
		
		clock_t   intime;//开始时间
		clock_t   outtime;//结束时间
		intime=clock();
		int i,j,t;
		for(j=0;j<size-1;j++)
			for(i=0;i<size-j;i++)
				if(a[i]>a[i+1])
				{
					t=a[i];
					a[i]=a[i+1];
					a[i+1]=t;
				}
		for(int k=0;k<size;k++)
		{
			cout<<setw(6)<<a[k]<<"    ";
		}
		outtime=clock();
		double tim=(outtime-intime)/(double)CLK_TCK;

		cout<<endl<<endl<<"排序结束。   总共耗时：   "<<tim<<"  秒"<<endl;
	}
	else if(opinion==2)
	{
		for(int i=0;i<size;i++)
			a[i]=rand();
		clock_t   intime;//开始时间
		clock_t   outtime;//结束时间
		intime=clock();
		heapsort(a,size);   //堆排序
		for(int k=0;k<size;k++)
		{
			cout<<setw(6)<<a[k]<<"    ";
		}
		outtime=clock();
		double tim=(outtime-intime)/(double)CLK_TCK;

		cout<<endl<<endl<<"排序结束。   总共耗时：   "<<tim<<"  秒"<<endl;
	}
	else if(opinion==3)
	{
		for(int i=0;i<size;i++)
			a[i]=rand();
		clock_t   intime;//开始时间
		clock_t   outtime;//结束时间
		intime=clock();
		shellsort(a,size);   //堆排序
		for(int k=0;k<size;k++)
		{
			cout<<setw(6)<<a[k]<<"    ";
		}
		outtime=clock();
		double tim=(outtime-intime)/(double)CLK_TCK;

		cout<<endl<<endl<<"排序结束。   总共耗时：   "<<tim<<"  秒"<<endl;
	}
	else if(opinion==4)
	{
		for(int i=0;i<size;i++)
			a[i]=rand();
		clock_t   intime;//开始时间
		clock_t   outtime;//结束时间
		intime=clock();
		shellsort(a,size);   //堆排序
		for(int k=0;k<size;k++)
		{
			cout<<setw(6)<<a[k]<<"    ";
		}
		outtime=clock();
		double tim=(outtime-intime)/(double)CLK_TCK;

		cout<<endl<<endl<<"排序结束。   总共耗时：   "<<tim<<"  秒"<<endl;
	}
	else
		exit(1);



	cout<<endl<<"操作完毕，按任意键进入下一次操作！→"<<endl;
	while (!kbhit());                             //调用库函数，等待用户按键
	system("cls");
	goto A;
	return 0;
}



//快速排序
void quicksort(int R[], int left,int right)
{
	int i=left,j=right;
	int temp=R[i];
	while(i<j)
	{
		while((R[j]>temp)&&(j>i))
		j=j-1;
		if(j>i)
		{
			R[i]=R[j];
			i=i+1;
		}
		while((R[i]<=temp)&&(j>i))
			i=i+1;
		if(i<j)
		{
			R[i]=R[j];
			j=j-1;
		}
	}
	//一次划分得到基准值的正确位置
	R[i]=temp;
	if(left<i-1) quicksort(R,left,i-1);  //递归调用左子区间
	if(i+1<right) quicksort(R,i+1,right);  //递归调用右子区间
}

//堆排序
void creatheap(int R[],int i,int n)     //建立大根堆
{
	int j;
	int t;
	t=R[i];
	j=2*i;
	while(j<n)
	{
		if((j<n)&&(R[j]<R[j+1]))
			j++;
		if(t<R[j])
		{
			R[i]=R[j];
			i=j;
			j=2*i;
		}
		else
			j=n;
		R[i]=t;
	}
}

void heapsort(int R[],int n)   //堆排序
{
	int t;
	for(int i=n/2;i>=0;i--)
		creatheap(R,i,n);
	for(i=n-1;i>=0;i--)
	{
		t=R[0];
		R[0]=R[i];
		R[i]=t;
		creatheap(R,0,i-1);
	}
}

void shellsort(int R[],int n)  //希尔排序
{
	for(int m=n/2;m>=1;m/=2)     //m表示增量大小，增量每次整除2，第一次为n/2
	{
		for(int i=m;i<n;i++)    //对每个元素直接插入到对应子序列的有序表中
		{
			int temp=R[i];  //将待插入对象暂存temp
			for(int j=i-m;j>=0;j-=m)    //在组内向前顺序进行比较和移动
			{
				if(temp<R[j])
					R[j+m]=R[j];
				else                     //查找到合适位置就退出j循环
					break;
			}
			R[j+m]=temp;
		}
	}
}