各位高手,小弟有一个还没有实现的程序,在VC环境下做的,不过以前学的是C现在刚学C++
所以主要语言格式是用C 做的,只有一些输入,输出流语句是C++格式的,由于初做这种程序,做的不太清晰,望大家多多见凉!
下面我说一下这个程序的要求:
(其实这是一个数据结构实验书上的题)
1.对6种常用的内部排序算法进行实测比较:起泡排序,直接插入排序,简单选择排序,快排,希尔排序,和堆排
2待排序表的元素的关键字为整数。用正序，逆序和不同乱序程度的不同数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数。
#include<iostream.h>
#include<stdio.h>
#include<math.h>
#define MAXSIZE 1000
#define SORTNUM 6
int i;
typedef void(*Func)(long c,long s);
//static Func Sorts[SORTNUM]={BubbleSort(long &c,long &s),InsertSort(long &c,long &s),SelectSort(long &c,long &s),QuickSort(long &c,long &s),ShellSort(long &c,long &s),HeapSort(long &c,long &s)};//6种排序算法
static char *SortNames[SORTNUM]={"Bubbl","Inser","Selec","Quick","Shell","Heap"};
static int Mix[]={0,1,4,16,64,128,256,512,4096};//构造各级乱序表时随机交换元素个数
typedef int DataType[MAXSIZE+2];
DataType data;//可排序表的顺序存储间
DataType data2;//辅助空间保留最新打乱的数据
int size;//表的当前长度
long compCount;//关键字的比较次数
long shiftCount;//关键字的移动次数
void BeforeSort()//每个排序算法在入口处调用
{
compCount=shiftCount=0;
}
Less(int i,int j)
{
compCount++;
return data[i]<data[j];
}
void Swap(int i,int j)
{
int x;
x=data[i];
data[i]=data[j];
data[j]=x;
shiftCount=shiftCount+3;
}
void Shift(int i,int j)
{
data[j]=data[i];
shiftCount++;
}
void CopyData(DataType list1,DataType &list2)
{
int i;
for(i=1;i<=size;i++)
list2[i]=list1[i];
}
void InverseOrder() //将可排序表置为逆序
{
int i;
for(i=1;i<=size;i++)
data[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++)
data[i]=data2[i]=i;
size=n;
}
compCount=shiftCount=0;
}
void RandomizeList(int d,int isInverse)
{
if(isInverse)
InverseOrder();
else InitList(size);
for(i=1;i<=Mix[d];i++)
data[(rand()%9000)+1]<-->data[(rand()%9000)+1];
CopyData(data,data2);
}
void RecallList() //恢复最后一次用RandomizeList随机打乱后的可排序表
{
CopyData(data2,data);
}
void BubbleSort(long &c,long &s) //起泡排序
{
BeforeSort();
do
{
swapped=FALSE;
for(i=1;i<=size-1;i++)
if(Less(i+1,i)){Swap(i+1,i);swapped=TRUE;}
}while(swapped);
c=compCount;s=shiftCount;
}
void InsertSort(long &c,long &s) //插入排序
{
BeforeSort();
for(i=1;i<=size-1;i++)
{
min=i;
for(j=i+1;i<=size;j++)
if(Less(j,min))
min=j;
if(i!=min)
Swap(i,min);
}
c=compCount;
s=shiftCount;
}
void SelectSort(long &c,long &s) //选择排序
{
BeforeSort();
for(i=1;i<=size-1;i++)
{min=i;
for(j=i+1;i<=size;j++)
if(less(j,min))
min=j;
if(i!=min)
Swap(i,min);
}
c=compCount;s=shiftCount;
}
void Qsort(int lo,int hi) //辅助函数
{
if(lo<hi)
{
i=lo;j=hi;m=(lo+hi)/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(lo,j);QSort(i,hi);
}
}
void QuickSort(long &c,long &s) //快速排序
{
BeforeSort();
QSort(1,size);
c=compCount;s=shiftCount;
}
void ShellSort(long &c,long &s) //希尔排序
{
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=compCount;s=shiftCount;
}
void Sift(int left,int right) //堆排序的调堆函数
{
i=left;j=2*i;Shift(left,0);finished=FALSE;
Shift(left,MAXSIZE+1);
while(j<=right&&!finished)
{
if(j<right&&less(j+1,j))j=j+1;
if(!less(j,0))finished=TRUE;
else{Shift(j,i);i=j;j=2*i;}
}
Shift(MAXSIZE+1,i);
}
void Heapsort(long &c,long &s)
{
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=compCount;s=shiftCount;
}
#define minGroup 8
#define maxGroup 18
static Func Sorts[SORTNUM]={BubbleSort(long &c,long &s),InsertSort(long &c,long &s),SelectSort(long &c,long &s),QuickSort(long &c,long &s),ShellSort(long &c,long &s),HeapSort(long &c,long &s)};
void Initialization()
{
randomize();
clrscr();//清屏
cout<<"****SortTest--1 Size(100-1000)--2 Groups(8-18)--3 Quit--q****";
size=400;
groups=18;
}
void ReadCommand(char &cmd)
{
do{cmd=getche();}while(cmd!='1'&&cmd!='2'&&cmd!='3'&&cmd!='q'&&cmd!='Q');
}
void Interpret(char cmd)
{
switch(cmd)
{
case'1'://显示测试结果比较表的表头，以下略去表格符号显示
for(i=0;i<=groups-1;i++)//逐组测试
{
if(i<groups/2)
RandomizeList(i,FALSE);//对正序表作i级打乱
else
Randomizelist(groups-i-1,TURE);//作逆序i级打乱
for(j=0;j<SORTNUM;j++)
{
RecallList()//还原数据
(*Sorts[j])(c,s);//测试第j种排序算法
//显示关键字比较次数C和移动次数S
GotoXY(6+(j-1)*6,i+7);printf("%6ld",c);
GotoXY(44+(j-1)*6,i+7);print("%6ld",s);
}//for j
}//for i
//显示测试结果比较表的相应部分表格符：
break;
case'2'://显示键入可排序表的长度的提示信息
scanf("%d",&n);
if(n<100)n=100;
if(n>1000)n=1000;
InitList(n);
break;
case'3'://显示键入测试的组数的提示信息
scanf("%d",&groups);
if(groups<minGroup) groups=minGroup;
if(groups>maxGroup) groups=maxGroup;
}
}
void main()
{
Initialzation();//初始化
do{
ReadCommand(cmd);
Interpret(cmd);
}while(cmd!='q'&&cmd!='Q');
}
