当前位置：文档库 › 第一次试验

第一次试验

#include
#include
#include
#include
#include
#define LIST_INIT_SIZE 30000
int bj1,yd1,n,com,mov;
long int A[7],B[7];
double t0,t1,t2,t3,t4,t5,C[5];
clock_t start_t,end_t;
typedef struct //结构体定义
{
int key;
}ElemType;
typedef struct //结构体定义
{
ElemType *elem;
int length;
}SqList;
void addlist(SqList &L) //生成随机数
{
int i;
a: printf("请输入你要输入的个数:");
scanf("%d",&n);
if(n>20000)
{
printf("超出范围重新输入!!!\n");
goto a;
}
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(0);
L.length=0;
for(i=1;i{
b: L.elem[i].key=rand();
if(L.elem[i].key>20000)goto b;
++L.length;
}
}
void SelectSort(SqList &L) //简单选择排序
{
start_t=clock();
int i,j,k,com=0,mov=0;
for(i=1;i{
k=i;
for(j=i+1;j{
com++;
if(L.elem[j].key}
if(i!=k)
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
mov+=3;
}
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",com,mov);

A[0]=com;
B[0]=mov;

}
void bubblesort(SqList &L) //冒泡排序
{
start_t=clock();
int i=1,j,com=0,mov=0;
while(i{
for(j=1;j{
com++;
if(L.elem[j].key>L.elem[j+1].key)
{
L.elem[0].key=L.elem[j].key;
L.elem[j].key=L.elem[j+1].key;
L.elem[j+1].key=L.elem[0].key;
mov+=3;
}
}
i++;
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",com,mov);

A[1]=com;
B[1]=mov;
}
void InsertSort(SqList &L) //直接插入排序
{
start_t=clock();
int i,j,com=0,mov=0;
for(i=2;i<=L.length;i++)
{
if(L.elem[i].key{
L.elem[0].key=L.elem[i].key;
mov++;
j=i-1;
com++;
while(L.elem[0].key{
L.elem[j+1].key=L.elem[j].key;
j--;
mov++;
com++;
}
L.elem[j+1].key=L.elem[0].key;
mov++;
}
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",com,mov);

A[2]=com;
B[2]=mov;

}
void xier(SqList &L) //希尔排序
{
start_t=clock();
int i,d=L.length/2,j,w=0,k,com=0,mov=0;
while(w{
w=1;
for(i=w;i{
k=i;
for(j=i+d;j{
com++;
if(L.elem[i].key>L.elem[j].key)
{
k=j;

}
}
if(i!=k)
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
mov+=3;
}
w++;
}
d=d/2;
w=1;
}
end_t=clock();
printf("比较次数为 %d移动次数为 %d\n",com,mov);

A[3]=com;
B[3]=mov;

}
void BeforeSort() //定义一个输出函数
{
yd1=0,bj1=0;
}

void display(int m,int n)
{
printf("比较次数为 %d移动次数为 %d\n",m,n);
}
int Partition(SqList L,int low,int high) //快速排序（递归）
{
int pivotkey;
L.elem[0]=L.elem[low];
yd1++;
pivotkey=L.elem[low].key;
while (low{
yd1++;
while(low=pivotkey)
{
--high;
L.elem[low]=L.elem[high];
bj1++;
yd1++;
}
while (low{
++low;
L.elem[high]=L.elem[low];
bj1++;
yd1++;
}
}
L.elem[low]=L.elem[0];
yd1++;
return low;
}
void QSort(SqList &L,int low,int high) //递归排序
{
int pivotloc;
if(low{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1); //递归
QSort(L,pivotloc+1,high); //递归
}
}
void QuickSort(SqList &L) //快速排序
{
start_t=clock();
BeforeSort();
QSort(L,1,L.length);
display(bj1,yd1);
end_t=clock();

A[4]=bj1;
B[4]=yd1;
}
void Merge(ElemType R[],ElemType R1[],int low,int m,int high) //归并排序（递归）
{
int i=low, j=m+1, k=low;
while(i<=m&&j<=high)
{
if(R[i].key<=R[j].key)
{
bj1++;
R1[k]=R[i];
yd1++;
i++;
k++;
}
else
{
bj1++;
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
while(i<=m)
{
R1[k]=R[i];
yd1++;
i++;
k++;
}
while(j<=high)
{
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
void MergePass(ElemType R[],ElemType R1[],int length, int n)
{
int i=0,j;
while(i+2*length-1{
Merge(R,R1,i,i+length-1,i+2*length-1); //递归
i=i+2*length;
}
if(i+length-1Merge(R,R1,i,i+length-1,n-1);
else
for(j=i;jR1[j]=R[j];
}
void MSort(ElemType R[],ElemType R1[],int n)
{
int length=1;
while (length{
MergePass(R,R1,length,n);
length=2*length;
MergePass(R1,R,length,n);
length=2*length;
}
}
void MergeSort(SqList &L) //归并排序
{
start_t=clock();
BeforeSort();
MSort(L.elem,L.elem,L.length);
display(bj1,yd1);
end_t=clock();

A[5]=bj1;
B[5]=yd1;

}
void heapAjust(ElemType R[],int root,int n) //堆排序
{

//root指向需要调整的父节点,n表示数组长度
int i = root;
int j = root*2;
int tmp;
while(j <= n)
{
if(j < n && R[j+1].key < R[j].key){
j = j+1;
bj1++;}
if(R[i].key > R[j].key)
{
bj1++;
tmp = R[i].key;
R[i].key = R[j].key;
R[j].key = tmp;
int i = j;
int j = i*2;
yd1=yd1+3;

}
else
{
j = n+1;
}
}
}
void hSort(ElemType R[],int n)
{
int i;
int tmp;
for(i = n/2;i > 0;i--)
{
heapAjust(R,i,n);
}
for(i = n; i > 1;i--)
{
tmp = R[i].key;
R[i].key = R[1].key;
R[1].key = tmp;
yd1=yd1+3;
heapAjust(R,1,i-1); //递归
}
}
void heapSort(SqList &L){ //堆排序
start_t=clock();
BeforeSort();
hSort(L.elem,L.length);
d

isplay(bj1,yd1);
end_t=clock();
A[6]=bj1;
B[6]=yd1;
}
void printf(SqList &L) //输出函数设定输出格式
{
long int d[6];
int i,n;
printf("\n★★★★★★比较次数★★★★★★\n"); //输出比较次数
printf("\n=====================\n");
for(i=0;i<6;i++){
d[i]= sqrt (A[i]/A[5]);}
printf("\n 归并排序： *");
printf("\n=====================\n");
printf(" 选择排序： ");
for(n=0,i=0;n<=d[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 冒泡排序： ");
for(n=0,i=1;n<=d[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 直插排序： ");
for(n=0,i=2;n<=d[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 希尔排序： ");
for(n=0,i=3;n<=d[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 快速排序： ");
for(n=0,i=4;n<=d[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 堆排序： ");
for(n=0,i=5;n<=d[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf("\n★★★★★★移动次数★★★★★★\n"); //输出移动次数
printf("\n=====================\n");
double e[6];
for(i=0;i<6;i++)
e[i]= sqrt (B[i]/B[5]);
printf("\n 希尔排序： *");
printf("\n=====================\n");
printf(" 选择排序： ");
for(n=0,i=0;n<=e[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 冒泡排序： ");
for(n=0,i=1;n<=e[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 直插排序： ");
for(n=0,i=2;n<=e[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 快速排序： ");
for(n=0,i=4;n<=e[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 归并排序： ");
for(n=0,i=5;n<=e[i];n++)
{
printf("*");
}
printf("\n=====================\n");
printf(" 堆排序： ");
for(n=0,i=6;n<=e[i];n++)
{
printf("*");
}
printf("\n=====================\n");

}
void shunxu(SqList &L){
int s[100];
s[0]=0;
for(int i=1;i<100;i++){
s[i]=s[i-1]+1;
}
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(0);
L.length=0;
for(int j=0;j<100;j++){
L.elem[j].key=s[j];
L.length=L.length+1;
}
}
void nixu(SqList &L){
int a[100];
a[0]=99;
for(int i=1;i<100;i++)
{
a[i]=a[i-1]-1;
}
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(0);
L.length=0;
for(int j=0;j<100;j++){
L.elem[j].key=a[j];
L.length=L.length+1;
}
}

void w(SqList &L) //可以返回主函数
{

int b;
printf("\n★★★★★★★★★★欢迎★★★★★★★★

★★★\n");
printf("\n请选择数据类型：1：随机 2：顺序 3：逆序 \n");
printf("\n***********************************************\n");
scanf("%d",&b);
switch(b){
case 1:{

addlist(L);
printf("\n选择排序: \n");
SelectSort(L);
addlist(L);
printf("\n冒泡排序: \n");
bubblesort(L);
addlist(L);
printf("\n直插排序: \n");
InsertSort(L);
addlist(L);
printf("\n希尔排序: \n");
xier(L);
addlist(L);
printf("\n快速排续: \n");
QuickSort(L);
addlist(L);
printf("\n归并排序: \n");
MergeSort(L);
addlist(L);
printf("\n堆排序: \n");
heapSort(L);
printf(L);
w(L); //返回主函数
};break;
case 2:{
shunxu(L);
printf("\n选择排序: \n");
SelectSort(L);
shunxu(L);
printf("\n起泡排序: \n");
bubblesort(L);
shunxu(L);
printf("\n直插排序: \n");
InsertSort(L);
shunxu(L);
printf("\n希尔排序: \n");
xier(L);
shunxu(L);
printf("\n快速排续: \n");
QuickSort(L);
shunxu(L);
printf("\n归并排序: \n");
MergeSort(L);
shunxu(L);
printf("\n堆排序: \n");
heapSort(L);
printf(L);
w(L); //返回主函数
};break;
case 3:{

nixu(L);
printf("\n选择排序: \n");
SelectSort(L);
nixu(L);
printf("\n起泡排序: \n");
bubblesort(L);
nixu(L);
printf("\n直插排序: \n");
InsertSort(L);
nixu(L);
printf("\n希尔排序: \n");
xier(L);
nixu(L);
printf("\n快速排续: \n");
QuickSort(L);
nixu(L);
printf("\n归并排序: \n");
MergeSort(L);
nixu(L);
printf("\n堆排序: \n");
heapSort(L);
printf(L);
w(L); //返回主函数
};break;
}

}
void main(){ //主函数

SqList L;
w(L);
}