sort.cpp

内部排序算法比较 一、需求分析 1． 实验要对以下6种常用的内部排序算法进行实测比较：起泡

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

#include "stdafx.h"
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#include<windows.h>


#define OK 0
#define mi 8
#define ma 18
#define MAXSIZE 1000
#define NUM 6
static char *Names[NUM]={"Bubbl","Inser","Selec","Quick","Shell","Heap"};
static int Mix[11]={0,1,4,16,64,128,256,512,1024,2048,4096};
typedef int Data[MAXSIZE+2];
#define FALSE 0
#define TRUE 1

Data data1;
Data data2;
int size;
long comp;
long shift;

void BeforeSort(){
	comp=shift=0;
}

int Less(int i,int j){
	comp++;
	return data1[i]<data1[j];
}

void Swap(int i,int j){
	int t;
	t=data1[i];
	data1[i]=data1[j];
	data1[j]=t;
	shift=shift+3;
}

void Shift(int i,int j){
	data1[j]=data1[i];
	shift++;
}

void CopyData(Data list1,Data &list2){
	int i;
	for(i=1;i<=size;i++)
		list2[i]=list1[i];
}

void InverseOrder(){
	int i;
	for(i=1;i<=size;i++)
		data1[i]=data2[i]=size-i+1;
}

void InitList(int n){
	int i;
	if(n<1) size=0;
	else{
		if(n>MAXSIZE) n=MAXSIZE;
		for(i=1;i<=n;i++)
			data1[i]=data2[i]=i;
		size=n;
	}
	comp=shift=0;
}

void RandomizeList(int d,int isInverse){
	int i,j=1;
		if(isInverse) InverseOrder();
		else InitList(size);
		for(i=1;i<=Mix[d];i++){ 
		 srand(size++);
			data1[i-1]=rand();
	
		}
			CopyData(data1,data2);
}

void RecallList(){
	CopyData(data2,data1);
}

void BubbleSort(long &c,long &s){
	int j,i;
	BeforeSort();
	do{
		j=FALSE;
		for(i=1;i<=size-1;i++)
			if(Less(i+1,i)){Swap(i+1,i);j=TRUE;}
		}while(j);
		c=comp;
		s=shift;
}


void InsertSort(long &c,long &s){
	    int i,j;
		BeforeSort();
		for(i=2;i<=size;i++){
			Shift(i,0);j=i-1;
			while(Less(0,j)) {Shift(j,j+1);j--;}
			Shift(0,j+1);
		}
		c=comp;
		s=shift;
}

void SelectSort(long &c,long &s){
			int i,j,m;
            BeforeSort();
			for(i=1;i<=size-1;i++){
				m=i;
				for(j=i+1;j<=size;j++)
					if(Less(j,m)) m=j;
					if(i!=m) Swap(i,m);
			}
		c=comp;
		s=shift;
}

void QSort(int p,int q){
	int i,j,m;
	if(p<q){
		i=p;j=q;m=(p+q)/2;
		do{
			while(Less(i,m)) i++;
			while(Less(m,j)) j--;
			if(i<=j){
				if(m==i)m=j;
				else if(m==j) m=i;
				Swap(i,j); i++; j--;
			}
		}while(i<=j);
		QSort(p,j); QSort(i,q);
	}
}

void QuickSort(long &c,long &s){
	 BeforeSort();
	 QSort(1,size);
	 c=comp;
	 s=shift;
}

void ShellSort(long &c,long &s){
	int i,h,j;
	BeforeSort();
	i=4;h=1;
	while(i<=size){i=i*2;h=2*h+1;}
	while(h!=0){
		i=h;
		while(i<=size){
			j=i-h;
			while(j>0&&Less(j+h,j)){
				Swap(j,j+h);j=j-h;
			}
			i++;
		}
		h=(h-1)/2;
	}
	c=comp;
	s=shift;
}

void Sift(int left,int right){
	int i,j,k;
	i=left; j=2*i; Shift(left,0);k=FALSE;
	Shift(left,MAXSIZE+1);
	while(j<=right && !k){
		if(j<right &&Less(j+1,j)) j=j+1;
		if(!Less(j,0)) k=TRUE;
		else {Shift(j,i);i=j;j=2*i;}
	}
	Shift(MAXSIZE+1,i);
}

void HeapSort(long &c,long &s){
	int left,right;
	BeforeSort();
	for(left=size/2;left>=1;left--) Sift(left,size);
	for(right=size;right>=2;right--)
	{Swap(1,right);Sift(1,right-1);}
	c=comp;
	s=shift;
}

int In(char cmd){
	switch(cmd){
	case '1':return TRUE;
	case '2':return TRUE;
	case '3':return TRUE;
	case 'q':return TRUE;
	case 'Q':return TRUE;
	default:return FALSE;
	}
}


void docmd(){
	      long c,s;
		  DWORD time11,time12,time21,time22,time31,time32,time41,time42,time51,time52,time61,time62;
	      RecallList();
          time11=GetTickCount();
		  BubbleSort(c,s);
	      printf("%s",Names[0]);
		  printf("%8d",c);
		  printf("%12d",s);
		  printf("\n");
		  time12=GetTickCount();
		  printf("滴答数为:\n");
		  printf("%ld\n",time12-time11);
		   RecallList();
		   time21=GetTickCount();
		  InsertSort(c,s);
	      printf("%s",Names[1]);
		  printf("%8d",c);
		  printf("%12d",s);
		  printf("\n");
		  time22=GetTickCount();
		  printf("滴答数为:\n");
		  printf("%ld\n",time22-time21);
		   RecallList();
		   time31=GetTickCount();
		  SelectSort(c,s);
	      printf("%s",Names[2]);
		  printf("%8d",c);
		  printf("%12d",s);
		  printf("\n");
			time32=GetTickCount();
		  printf("滴答数为:\n");
		  printf("%ld\n",time32-time31);
		  RecallList();
		  time41=GetTickCount();
	
		  QuickSort(c,s);
	      printf("%s",Names[3]);
		  printf("%8d",c);
		  printf("%12d",s);
		  printf("\n");
		  time42=GetTickCount();
		  printf("滴答数为:\n");
		  printf("%ld\n",time42-time41);
		  RecallList();
		  time51=GetTickCount();
		  ShellSort(c,s);
	      printf("%s",Names[4]);
		  printf("%8d",c);
		  printf("%12d",s);
		  printf("\n");
		  time52=GetTickCount();
		  printf("滴答数为:\n");
		  printf("%ld\n",time52-time51);
		  RecallList();
		  time61=GetTickCount();
		  HeapSort(c,s);
		  printf("\n");
	      printf("%s",Names[5]);
		  printf("%8d",c);
		  printf("%12d",s);
		  printf("\n");
		  time62=GetTickCount();
		  printf("滴答数为:\n");
		  printf("%ld\n",time62-time61);
}
		

void main(){
	char cmd;
	
	 printf("1.SIZE(100-10000000)\n");
	 printf("2.GROUPS(8-18)\n");
	 printf("3.SORTTEST\n");
	 printf("按Q退出\n");
	int i,n,groups;

	do{
			printf("请输入你的命令符\n");
    do{
		cmd=getchar();
	}while(!In(cmd));
	switch(cmd){
		case '1':printf("请输入可排序表的长度的提示信息\n");
				   scanf("%d",&n);
					if(n<100) n=100;
					if(n>10000000) n=10000000;
					InitList(n);						
			break;
	    case '2':printf("请输入测试的组数的提示信息\n");
			scanf("%d",&groups);
			if(groups<mi) groups=mi;
			if(groups>ma) groups=ma;
			break;
		case '3':for(i=0;i<=groups-1;i++){
			if(i<groups/2)
				RandomizeList(i,FALSE);
			else
				RandomizeList(groups-i-1,TRUE);
			printf("\n");
			printf("第%d次六种比较\n", i+1);
			printf("排序名   比较次数   移动次数\n");
			docmd();
			printf("\n");
			
		}
		break;
	    
	}
	}while (cmd!='q' && cmd!='Q');
}