pan.cpp

有以下七种排序法的实现方法

#include <stdio.h>
#include "time.h"
#include <windows.h>
#include<iostream>
#include<stdlib.h>
#include<ctime>
using namespace std;
void Insertsort(int num[],int n);//顺序插入
void quick(int num[],int n);
void Insert(int num[],int n);//折半插入
void Shellsort(int num[],int n);//希尔排序
void Bubblesort(int num[],int n);//冒泡排序
void Quicksort(int num[],int first,int end,int &q,int &b);//快速排序
void selectsort(int num[],int n);//选择排序
int par(int num[],int i,int j,int &q,int &b);
void Merge(int r[],int r1[],int s,int m,int t,int &move,int &com);//归并排序
void MergePass(int r[],int r1[],int n,int h,int &move,int &com);
void MergeSort(int r[],int r1[],int n,int &move,int &com);
void merge(int r[],int n);//归并辅助函数
void print(int array[],int n)//打印
{
	for(int i=1;i<=n;i++)//显示方法 每行5个数据。
	{
		cout<<"  "<<array[i];
		if(i%5==0) cout<<endl; 
	}
	
	cout<<endl;
}
void main()
{
	int a[1110],b[1110],c[1110],d[1110],e[1110],f[1110],g[1110];
	int choice;	
	srand((unsigned)time(NULL));//建立随机数据数组。
	for(int i=0;i<=1000;i++)
	{
		g[i]=f[i]=e[i]=d[i]=c[i]=b[i]=a[i]=rand();
		
		
	}			
	cout<<"\n请选择排序方式:1冒泡排序,2顺序插入排序,3快速排序,4折半插入排序,5希尔排序,6.选择排序,7归并排序,8退出"<<endl;
	cin>>choice;
	do{
		switch(choice)
		{
		case 1:	
			
			cout<<"原始数据：\n";
			print(a,1000);
			cout<<"排序后：\n";
			Bubblesort(a,1000);
			cout<<"\n请选择排序方式:1冒泡排序,2顺序插入排序,3快速排序,4折半插入排序,5希尔排序,6.选择排序,7归并排序,8退出"<<endl;
			cin>>choice;
			break;
		case 2:
			cout<<"原始数据：\n";
			print(b,1000);
			cout<<"排序后：\n";
			Insertsort(b,1000);
			cout<<"\n请选择排序方式:1冒泡排序,2顺序插入排序,3快速排序,4折半插入排序,5希尔排序,6.选择排序，7退出"<<endl;
			cin>>choice;
			break;
		case 3:
			quick(c,1000);
			
			cout<<"\n请选择排序方式:1冒泡排序,2顺序插入排序,3快速排序,4折半插入排序,5希尔排序,6.选择排序,7归并排序,8退出"<<endl;
			cin>>choice;
			break;
		case 4:
			cout<<"原始数据：\n";
			print(d,1000);
			cout<<"排序后：\n";
			Insert(d,1000);
			cout<<"\n请选择排序方式:1冒泡排序,2顺序插入排序,3快速排序,4折半插入排序,5希尔排序,6.选择排序,7归并排序,8退出"<<endl;
			cin>>choice;
			break;
		case 5:
			cout<<"原始数据：\n";
			print(e,1000);
			cout<<"排序后：\n";			
			Shellsort(e,1000);						
			cout<<"\n请选择排序方式:1冒泡排序,2顺序插入排序,3快速排序,4折半插入排序,5希尔排序,6.选择排序,7归并排序,8退出"<<endl;
			cin>>choice;
			break;
		case 6:	
			
			cout<<"原始数据：\n";
			print(f,1000);
			cout<<"排序后：\n";
			selectsort(f,1000);
			cout<<"\n请选择排序方式:1冒泡排序,2顺序插入排序,3快速排序,4折半插入排序,5希尔排序,6.选择排序,7归并排序,8退出"<<endl;
			cin>>choice;
			break;
		case 7:
			merge(g,1000);			
			cout<<"\n请选择排序方式:1冒泡排序,2插入排序,3快速排序,4选择排序,5希尔排序,6折半插入排序,7归并排序,8退出"<<endl;	
			cin>>choice;
			break;
		default: break;
		}
	}while(choice!=8&&choice<9);
	cout<<"Thank you for your using!"<<endl;
}
void Insertsort(int num[],int n)
{
	int p=0;
	int q=0;
	LARGE_INTEGER     litmp   ;   
    LONG64		QPart1,QPart2   ;   
    double		d=0;   
    QueryPerformanceCounter(&litmp)   ;     
    //   获得初始值   
	QPart1   =   litmp.QuadPart; 
	for(int i=2;i<=n;i++,p++)
	{
		if(num[i]<num[i-1])
		{
			num[0]=num[i];
			q++;
			//num[i]=num[i-1];
			//	q++;
			for(int j=i-1;num[0]<num[j];p++,j--,q++)
			{
				num[j+1]=num[j];
				//q++;
			}
			p--;q--;
			num[j+1]=num[0];
			q++;
		}
		p++;
	}
	p--;
	QueryPerformanceCounter(&litmp)   ;     
	QPart2   =   litmp.QuadPart   ;   
	d=(double)(QPart2   -   QPart1);
	for(int m=1;m<=n;m++)
	{
		cout<<num[m]<<"  ";
		if(m%5==0) cout<<endl;
	}
	cout<<endl;
	
	cout<<"移动次数:"<<q;
	cout<<endl;
	cout<<"比较次数:"<<p;
	cout<<endl;
	cout<<"排序所用时间为："<<d<<endl;
}
void Shellsort(int num[],int n)
{
	int p=0;
	int q=0;
	LARGE_INTEGER     litmp   ;   
    LONG64		QPart1,QPart2   ;   
    double		time=0;   
    QueryPerformanceCounter(&litmp)   ;     
    //   获得初始值   
	QPart1   =   litmp.QuadPart   ; 
	for(int d=n/2;d>=1;d=d/2)
	{
		for(int i=d+1;i<=n;i++,p++)
		{
			if(num[i]<num[i-d])
			{
				num[0]=num[i];
				q++;
				int j=0;
				for(j=i-d;j>0&&num[0]<num[j];p++,j=j-d)
				{
					num[j+d]=num[j];
					q++;
				}
				p--;
				num[j+d]=num[0];
				q++;
			}
		}
		p--;
	}
	QueryPerformanceCounter(&litmp)   ;     
	QPart2   =   litmp.QuadPart   ;   
	time=(double)(QPart2   -   QPart1);
	for(int m=1;m<=n;m++)
	{
		cout<<num[m]<<"  ";
		if(m%5==0) cout<<endl;
	}
	cout<<"排序所用时间为："<<time<<endl;
	cout<<endl;
	cout<<"移动次数:"<<q<<endl;
	cout<<"比较次数:"<<p<<endl;
}
void Bubblesort(int num[],int n)
{
	int p=0;
	int k=0;
	int pos=n;
	int right=pos;
	LARGE_INTEGER     litmp   ;   
    LONG64		QPart1,QPart2   ;   
    double		d=0;   
    QueryPerformanceCounter(&litmp)   ;     
    //   获得初始值   
	QPart1   =   litmp.QuadPart   ; 
	while(pos)
	{
		pos=0;
		for(int j=1;j<right;j++,p++)
			if(num[j]>num[j+1])
			{
				
				int a=num[j];
				num[j]=num[j+1];
				k++;
				num[j+1]=a;
				k++;
				pos=j;
			}
			p--;
	}
	QueryPerformanceCounter(&litmp)   ;     
	QPart2   =   litmp.QuadPart   ;   
	d=(double)(QPart2   -   QPart1);
	for(int m=1;m<=n;m++)
	{
		cout<<num[m]<<"  ";
		if(m%5==0) cout<<endl;
	}
	cout<<endl;
	cout<<"移动次数:"<<k<<endl;
	cout<<"比较次数:"<<p<<endl;
	cout<<"排序所用时间为："<<d<<endl;
}

int par(int r[] , int i, int j,int &q,int &b)
{
	int pivot = r[i];                  //选取基准记录
	while (i<j)
	{
		while((i<j) && (r[j]>=pivot)&&++b)    //右侧扫描
			j--;
		r[i] = r[j];
		q++;
		while((i<j) && (r[i]<=pivot)&&++b)     //左侧扫描
			i++;
		r[j] =r[i];
		q++;
	}
	r[i]=pivot;
	q++;
	return i;
}


void Quicksort(int num[],int first,int end,int &q,int &c)
{
	
	if(first<end)
	{
		int b=par(num,first,end,q,c);
		Quicksort(num,first,b-1,q,c);
		Quicksort(num,b+1,end,q,c);
	}
	
	
}
void Insert(int num[],int n)
{
	int p=0;
	int q=0;
	int mid=0;
	LARGE_INTEGER     litmp   ;   
    LONG64		QPart1,QPart2   ;   
    double		d=0;   
    QueryPerformanceCounter(&litmp)   ;     
    //   获得初始值   
	QPart1   =   litmp.QuadPart   ; 
	for(int i=2;i<=n;i++,p++)
	{
		int low=1;
		int  high=i-1;
		int m=1;
		if(num[i]<num[i-1])
		{
			num[0]=num[i];
			q++;
			while(low<=high&&m)
			{
				mid=(low+high)/2;
				p++;
				if(num[0]<num[mid])
					high=mid-1;
				else if(num[0]>num[mid])
					low=mid+1;
				else
					m=0;
			}
			
			for(int k=i-1;k>=mid;k--,q++)//=mid
				num[k+1]=num[k];
			q--;
			num[k+1]=num[0];	
			q++;
		}
	}
	p--;
	QueryPerformanceCounter(&litmp)   ;     
	QPart2   =   litmp.QuadPart   ;   
	d=(double)(QPart2   -   QPart1);
	for(int l=1;l<=n;l++)
	{
		cout<<num[l]<<"  ";
		if(l%5==0) cout<<endl;
	}
	cout<<endl;
	
	cout<<"移动次数:"<<q;
	cout<<endl;
	cout<<"比较次数:"<<p;
	cout<<endl;
	cout<<"排序所用时间为："<<d<<endl;
	
}
void selectsort(int num[],int n)
{
	int p=0;
	int q=0;
	LARGE_INTEGER     litmp   ;   
    LONG64		QPart1,QPart2   ;   
    double		d=0;   
    QueryPerformanceCounter(&litmp)   ;     
    //   获得初始值   
	QPart1   =   litmp.QuadPart   ; 
	for(int i=1;i<=n;i++)
	{
		int d=i;
		for(int j=i+1;j<=n;j++,p++)
			if(num[j]<num[d])
				d=j;
			if(d!=i)
			{
				q+=3;
				num[0]=num[i];
				num[i]=num[d];
				num[d]=num[0];
			}
			p--;
	}
	QueryPerformanceCounter(&litmp)   ;     
	QPart2   =   litmp.QuadPart   ;   
	d=(double)(QPart2   -   QPart1);
	for(int m=1;m<=n;m++)
	{
		cout<<num[m]<<"  ";
		if(m%5==0) cout<<endl;
	}
	
	cout<<endl;
	cout<<"移动次数:"<<q<<endl;
	cout<<"比较次数:"<<p<<endl;
	cout<<"排序所用时间为："<<d<<endl;
}
void quick(int num[],int n)
{
	int g=0;
	int h=0;
	cout<<"原始数据：\n";
	print(num,n);
	LARGE_INTEGER     litmp   ;   
	LONG64		QPart1,QPart2   ;   
			 double		time1=0;   
			 QueryPerformanceCounter(&litmp)   ;     
			 //   获得初始值   
			 QPart1   =   litmp.QuadPart   ; 
			 Quicksort(num,1,n,g,h);
			 QueryPerformanceCounter(&litmp)   ;     
			 QPart2   =   litmp.QuadPart   ;   
			 time1=(double)(QPart2   -   QPart1);
			 cout<<"排序后：\n";
			 print(num,n);
			 cout<<"移动次数:"<<g;
			 cout<<endl;
			 cout<<"比较次数:"<<h;
			 cout<<endl;
			 cout<<"排序所用时间为："<<time1<<endl;
}
void Merge(int r[],int r1[],int s,int m,int t,int &move,int &com)
{
	int i=s,j=m+1,k=s;
	while(i<=m&&j<=t)
	{
		
		com++;
		if(r[i]<=r[j])
		{
			r1[k++]=r[i++];
			move++;
		}
		
		else
		{
			
			r1[k++]=r[j++];
			move++;
		}
	}
	if(i<=m)
	{
		while(i<=m)
		{
			r1[k++]=r[i++];
			move++;
		}
	}
	else
	{
		while(j<=t)
		{
			r1[k++]=r[j++];
			move++;
		}
	}
} 
void MergePass(int r[],int r1[],int n,int h,int &move,int &com)
{
	int i=1;
	while(i<=n-2*h+1)
	{
		Merge(r,r1,i,i+h-1,i+2*h-1,move,com);
		i+=2*h;

	}
	if(i<n-h+1) Merge(r,r1,i,i+h-1,n,move,com);
	else 
		for(int k=i;k<=n;k++)
		{
			r1[k]=r[k];
		}
}
void MergeSort(int r[],int r1[],int n,int &move,int &com)
{
	int h=1;
	while(h<n)
	{
		MergePass(r,r1,n,h,move,com);
		h=2*h;
		for(int i=1;i<=n;i++)
		{
			r[i]=r1[i];
		}
	}
}
void merge(int r[],int n)
{
	int m=0;
	int l=0;
	int r1[1100]={0};
	cout<<"原始数据：\n";
	print(r,n);
	LARGE_INTEGER     litmp   ;   
    LONG64		QPart1,QPart2   ;   
    double		d=0;   
    QueryPerformanceCounter(&litmp)   ;     
    //   获得初始值   
	QPart1   =   litmp.QuadPart   ;   
	MergeSort(r,r1,n,m,l);
	QueryPerformanceCounter(&litmp)   ;     
	QPart2   =   litmp.QuadPart   ;   
	d=(double)(QPart2   -   QPart1);  
	cout<<"排序后：\n";
	print(r,n);
	cout<<"移动次数:"<<m;
	cout<<endl;
	cout<<"比较次数:"<<l;
	cout<<endl;
	cout<<"运行时间:"<<d<<endl;
}