sort.cpp

排序程序,包含快速排序、归并排序、谢尔排序、插入排序。输出了比较次数和移动次数。

// Sort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <fstream.h>
#include <string>
#include <windows.h>

#define Num 100000
using std::string;

int array[Num];
int saveArray[Num];
unsigned long static swapt=0;
unsigned long static compare=0;

int readArray(string fileName)
{
	int number,i=0;
	ifstream infile(fileName.c_str());
	if(!infile)
	{
		cerr<<"错误：无法打开输入文件"<<endl;
		return -1;
	}
	while(infile>>number)
	{
		array[i]=number;
		saveArray[i]=number;
		i++;
	}
	infile.close();
	if(i!=Num)
	{
		cerr<<"错误：读入数字个数不足"<<endl;
		return -1;
	}

	cout<<endl<<"读取文件"<<fileName.c_str()<<"成功，共有"<<Num<<"个数"<<endl;

	return 0;
}

void quick(int Key[],int left, int right)
{
	int i=left,j=right,t=Key[i];
	if(left<right)
	{
		i=left;
		j=right;
	}
	
	while(i<j)								/*判断是否划分完毕*/
	{
		while(i<j&&Key[j]>t)				/*右指针向左移动直到找到比t下标小的元素*/
		{
			compare++;
			j--;
		}
		if(i<j)								/*若左右指针指向不同元素把比t小的元素插到左指针指向的元素位置*/
		{
			swapt++;
			Key[i]=Key[j];
			i++;
		}
		while(i<j&&Key[i]<t)               /*若左右指针指向不同元素左指针向右移动直到找到比t下标大的元素*/
		{
			i++;
			compare++;
		}
		if(i<j)								/*把比t小的元素插到左指针指向的元素位置*/
		{
			swapt++;
			Key[j]=Key[i];
			j--;
		}
	}
	swapt++;
	Key[i]=t;								/*把t下标元素插入到左右指针共同指向的位置*/
	if(left<i-1)							/*若划分的左数据段多于一个元素则再次排序*/
		quick(Key,left,i-1);				/*递归调用函数把划分的左数据段排序*/
	if(i+1<right)							/*若划分的右数据段多于一个元素则再次排序*/
		quick(Key,i+1,right);				/*递归调用函数把划分的右数据段排序*/
}
void quickSort(int Key[])					/*快速排序 */
{
	unsigned long start_time=GetTickCount(); 
	swapt=0;
	compare=0;
	quick(Key,0,Num-1);
	unsigned long end_time = GetTickCount(); 
	unsigned long elapse_time = end_time - start_time;
	cout<<"快速排序比较了"<<compare<<"次,移动了"<<swapt<<"次,耗费时间"<<elapse_time<<"ms"<<endl;
}

void swap(int *data1,int *data2)	/*data1,*data2分别为指向变量的指针*/
{
	*data1+=*data2;					/*交换变量的过程*/
	*data2=*data1-*data2;
	*data1-=*data2;
}

void merge(int Key[],int tempKey[], int s,int u,int v)	/*将有序的X[s..u]和X[u+1..v]归并为有序的X[s..v]*/
{
	int i=s,j=u+1,q=s;
	while(i<=u&&j<=v)				 /*两有序表是否有任一表已扫描完*/
	{
		compare++;
		swapt++;
		if(Key[i]<=Key[j])			 /*若表一元素比表二元素大，把表二元素插入到表一*/	
			tempKey[q++]=Key[i++];
		else
			tempKey[q++]=Key[j++];
	}
	while(i<=u)
		tempKey[q++]=Key[i++];
	while(j<=v)
		tempKey[q++]=Key[j++];
}

void mergePass(int Key[],int tempKey[], int l)		/*一趟归并函数*/
{
	int i,j;
	for(i=0;i+2*l-1<Num;i+=2*l)		/*把数组分多组进行一次归并*/
		merge(Key,tempKey,i,i+l-1,i+2*l-1);
	if(i+l-1<Num)						  /*多次归并表二元素比表一少的一次归并*/
		merge(Key,tempKey,i,i+l-1,Num-1);
	else							  /*归并后剩下一组的一次归并*/
		for(j=i;j<Num;j++)
			tempKey[j]=Key[j];
}
void mergeSort(int Key[])		 /*归并排序*/
{
	int l=1;
	int tempKey[Num];
	bool isKeyArray=false;
	unsigned long start_time=GetTickCount(); 
	swapt=0;
	compare=0;
	mergePass(Key,tempKey,l);
	while(l<Num)						/*进行多次一趟归并*/
	{
		mergePass(Key,tempKey,l);
		isKeyArray=false;
		l*=2;
		if(l<=Num)
		{
			isKeyArray=true;
			mergePass(tempKey,Key,l);
		}
		l*=2;
	}

	if(!isKeyArray)		/*如果合并的结果不在Key中，需要从tempKey中导入到Key*/
		for(int i=0;i<Num;i++)
			Key[i]=tempKey[i];

	unsigned long end_time = GetTickCount(); 
	unsigned long elapse_time = end_time - start_time;
	cout<<"插入排序比较了"<<compare<<"次,移动了"<<swapt<<"次,耗费时间"<<elapse_time<<"ms"<<endl;
}

void insertSort(int Key[])	/*插入排序*/
{
	int i,j,temp;
	compare=0;
	swapt=0;
	unsigned long start_time=GetTickCount(); 
	for(i=1;i<Num;i++)				/*从未排序部分取一元素*/
	{
		temp=Key[i];
		j=i-1;
		while(j>=0&&temp<Key[j])    /*有序部分后移腾出一元素空间*/
		{
			compare++;
			swapt++;
			Key[j+1]=Key[j];
			j--;
		}
		swapt++;
		Key[j+1]=temp;             /*把取出的元素插入到已排序部分*/
	}
	unsigned long end_time = GetTickCount(); 
	unsigned long elapse_time = end_time - start_time;
	cout<<"插入排序比较了"<<compare<<"次,移动了"<<swapt<<"次,耗费时间"<<elapse_time<<"ms"<<endl;
}

void shellSort(int Key[])  /*谢尔排序*/
{
	int i,j,flag,gap=Num;
	swapt=0;
	compare=0;
	unsigned long start_time=GetTickCount(); 
	while(gap>0)                  /*判断距离是否为零*/
	{
		gap/=2;                     /*缩小元素间距离*/
		do{
			flag=0;
			for(i=0;i<Num-gap;i++)
			{
				j = i+gap;
				compare++;
				if(Key[i]>Key[j])
				{
					swapt++;
					swap(Key+i,Key+j);
					flag = 1;
				}
			}
		}while(flag!=0);
			
	}
	unsigned long end_time = GetTickCount(); 
	unsigned long elapse_time = end_time - start_time;
	cout<<"谢尔排序比较了"<<compare<<"次,移动了"<<swapt<<"次,耗费时间"<<elapse_time<<"ms"<<endl;
}

int main(int argc, char* argv[])
{
	int i;
	cout<<"排序开始，总共有五个文件，每个文件中存储了100000个1-32768之间的随机数"<<endl;
	for(i=1;i<=5;i++)
	{
		int j;
		
		string fileName("file");
		char numString[5];
		_itoa(i,numString,10);
		fileName = fileName + numString + ".txt";
		if(readArray(fileName))
			break;	

		cout<<"快速排序:"<<endl;
		quickSort(array);	//快速排序

		cout<<"归并排序:"<<endl;
		for(j=0;j<Num;j++)
		{
			array[j]=saveArray[j];
		}
		mergeSort(array);	//归并排序

		cout<<"谢尔排序:"<<endl;
		for(j=0;j<Num;j++)
		{
			array[j]=saveArray[j];
		}
		shellSort(array);	//谢尔排序

		cout<<"插入排序:"<<endl;
		for(j=0;j<Num;j++)
		{
			array[j]=saveArray[j];
		}
		insertSort(array);	//插入排序

	}

	getchar();
	return 0;
}