📄 sort.cpp
字号:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 2300
typedef int KeyType;
typedef int InfoType;
typedef struct{
KeyType key;
InfoType otherinfo;
}RcdType;
typedef struct{
RcdType r[MAXSIZE+1];
long length;
}SqList;
SqList CreaList ()
{//建立
long i;
SqList L;
for(i=1;i<MAXSIZE+1;i++)
{
L.r[i].key=(rand()%MAXSIZE);
}
L.length=MAXSIZE;
return L;
}//建立
void PrintfList(SqList * L)
{//打印
long i;
for(i=1;i<MAXSIZE+1;i++)
{
printf("%8d",L->r[i].key);
}
}
//1折半
SqList BInsertSort(SqList L,long bj1[],long jh1[])
{
bj1[0]=0;jh1[0]=0;
long i,j,low,high,k;
for(i=2; i<=L.length; ++i)
{
L.r[0]=L.r[i];
jh1[0]+=1;
low=1;high=i-1;
while(low<=high)
{
k=(low+high)/2;
if(L.r[0].key <L.r[k].key)
{high=k-1;bj1[0]+=1;}
else {low=k+1;bj1[0]+=1;}
}
for(j=i-1;j>=high+1;j--)
{ L.r[j+1]=L.r[j];jh1[0]+=1;}
L.r[high+1]=L.r[0];
jh1[0]+=1;
}
return L;
}//折半
//2直接
SqList InsertSort(SqList L,long bj2[],long jh2[])
{
long j,k;
bj2[0]=0;
jh2[0]=0;
for(k=2; k<=L.length; ++k)
if(L.r[k].key< L.r[k-1].key )
{
bj2[0]+=1;
L.r[0] = L.r[k];
L.r[k]=L.r[k-1];
jh2[0]+=2;
for(j=k-2; L.r[0].key<L.r[j].key; --j)
{
L.r[j+1]=L.r[j]; jh2[0]+=1;bj2[0]+=1;
}
L.r[j+1]=L.r[0];
jh2[0]+=1;
}
else bj2[0]+=1;
return L;
}//直接
//3冒泡
SqList Bubble(SqList L,long bj3[],long jh3[])
{
long i,j;
bj3[0]=0;
jh3[0]=0;
for(j=L.length;j>=2;j--)
for(i=1;i<j;i++)
{ if(L.r[i].key>L.r[i+1].key)
{
L.r[0]=L.r[i];
L.r[i]=L.r[i+1];
L.r[i+1]=L.r[0];
jh3[0]+=3;
bj3[0]+=1;
}
else bj3[0]+=1;
}
return L;
}//冒泡
//4堆排序
SqList HeapAdjust(SqList L,int s,int m ,long bj4[],long jh4[])
{//建堆
RcdType rc;
long j;
rc=L.r[s];
for(j=2*s;j<=m;j*=2)
{
if(j<m&&L.r[j].key<L.r[j+1].key)
{
j++;
if(j<m) bj4[0]+=1;
}
if(L.r[j].key<rc.key)
{
bj4[0]+=1;
break;
}
L.r[s]=L.r[j];
jh4[0]+=1;
s=j;
}
L.r[s]=rc;
jh4[0]+=1;
return L;
}
SqList HeapSort(SqList L,long bj4[],long jh4[])
{//堆排序
long i;
bj4[0]=0;
jh4[0]=0;
for (i=L.length/2;i>0;i--)
L=HeapAdjust(L,i,L.length,bj4,jh4);
for(i=L.length;i>1;i--)
{
L.r[0]=L.r[i];
L.r[i]=L.r[1];
L.r[1]=L.r[0];
jh4[0]+=3;
L=HeapAdjust(L,1,i-1,bj4,jh4);
}
return L;
}
//堆排序
//5简单选择排序
SqList SeledSort(SqList L,long bj5[],long jh5[])
{
long i,j,k;
bj5[0]=0;
jh5[0]=0;
for(i=1; i<=L.length; ++i)
{
j=i;
for(k=i+1; k<=L.length; ++k)
{
if(L.r[k].key<L.r[j].key)
{
{j=k;bj5[0]+=1;}
if(i!=j)
{
L.r[0] = L.r[i];
L.r[i] = L.r[j];
L.r[j] = L.r[0];
jh5[0]+=3;
}
}
else bj5[0]+=1;
}
}
return L;
}//简单选择排序
//6希尔
SqList ShellSort(SqList L,int dk ,long bj6[],long jh6[])
{
long i,j;
for(i=1+dk;i<=L.length;i++)
{
if(L.r[i].key<L.r[i-dk].key)
{
L.r[0]=L.r[i];
jh6[0]+=1;
bj6[0]+=1;
for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
{
{
L.r[j+dk]=L.r[j];jh6[0]+=1;
if(j>0)bj6[0]+=1;
}
L.r[j+dk]=L.r[0];
jh6[0]+=1;
}
}
else bj6[0]+=1;
}
return L;
}
SqList ShallSort(SqList L,long bj6[],long jh6[])
{
jh6[0]=0;
bj6[0]=0;
int dlta[]={64,32,16,8,4,2,1};
long i;
for(i=0;i<7;i++)
L=ShellSort(L,dlta[i],bj6,jh6);
return L;
}//希尔
//7归并
void Merge(RcdType sr[],RcdType tr[],int i,int m,int n)
{//7归并
long j,k,p;
for(j=m+1,k=i;i<=m&&j<=n;k++)
{
if(sr[i].key<=sr[j].key)
tr[k]=sr[i++];
else
tr[k]=sr[j++];
}
if(i<=m)
for(p=i;p<=m;p++)
tr[k+p-i]=sr[p];
if(j<=n)
for(p=j;p<=n;p++)
tr[k+p-j]=sr[p];
}
void MSort(RcdType sr[],RcdType tr1[],int s,int t)
{
long m;
RcdType tr2[MAXSIZE];
if(s==t)
tr1[s]=sr[s];
else
{
m=(s+t)/2;
MSort(sr,tr2,s,m);
MSort(sr,tr2,m+1,t);
Merge(tr2,tr1,s,m,t);
}
}
void MergeSort(SqList *L,long bj7[],long jh7[])
{
bj7[0]=0;
jh7[0]=0;
MSort((*L).r,(*L).r,1,(*L).length);
}//归并
//8快速
int Partition(SqList * L,int low,int high,long bj8[],long jh8[])
{//快排
long pivotkey;
L->r[0].key=L->r[low].key;
pivotkey=L->r[low].key;
jh8[0]+=2;
while(low<high)
{
while(low<high && pivotkey<=(L->r[high].key))
{--high;if(low<high)bj8[0]+=1;}
{L->r[low].key=L->r[high].key;jh8[0]+=1;}
while(low<high && (L->r[low].key)<=pivotkey)
{++low;if(low<high)bj8[0]+=1;}
{ L->r[high].key=L->r[low].key;jh8[0]+=1;}
}
{L->r[low].key=L->r[0].key ;jh8[0]+=1;}
return low;
}
void QSort(SqList * L,int low,int high,long bj8[],long jh8[] )
{
long pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high, bj8,jh8);
QSort(L,low,pivotloc-1, bj8,jh8 );
QSort(L,pivotloc+1,high, bj8,jh8 );
}
}
SqList QuickSort(SqList L,long bj8[],long jh8[] )
{
bj8[0]=0;
jh8[0]=0;
QSort(&L,1,L.length, bj8,jh8 );
return L;
}
//快速
void time( void )
{//时间
struct tm *newtime;
char tmpbuf[128];
time_t lt1;
time( <1 );
newtime=localtime(<1);
strftime( tmpbuf, 128, " 今天是： %A, day %d of %B in the year %Y.\n", newtime);
printf(tmpbuf);
}
void time1(void)
{//时间
struct tm *ptr;
time_t lt;
lt =time(NULL);
ptr=gmtime(<);
printf(" 现在是：");
printf(ctime(<));
}
main()
{
long i,n,k;
SqList L,Q;
long bj1[1],bj2[1],bj3[1],bj4[1],bj5[1],bj6[1],bj7[1],bj8[1];//比较
long jh1[1],jh2[1],jh3[1],jh4[1],jh5[1],jh6[1],jh7[1],jh8[1];//交换
clock_t start1,start2,start3, start4,start5, start6,start7, start8;//开始
clock_t finish1,finish2,finish3,finish4,finish5,finish6,finish7,finish8;//结束
//long start,finish;
long m,t;
SqList CreaList ();
printf("\n 欢迎来到孔刚和侯光林的数据结构程序设计中。\n 请多多指导。发E_mail到whhxkg@yahoo.com.cn谢谢。\n");
time();
time1();
printf("30000个数没能实现。暂时只实现2400个数。希望老师能给分析一下。给个结论。谢谢！");
start1: printf("\n请选择：\n1.进入；\n2.退出。\n");
scanf("%d",&n);
if(n==1)
{
start: printf("\n请选择：\n0.全部排序；\n1.折半插入排序；\n2.直接插入排序；\n3.冒泡排序；\n4.堆排序；");
printf("\n5.简单选择排序；\n6.希尔排序；\n7.归并排序(暂时有错误！希望老师能给调试一下。！)；\n8.快速排序；\n9.退出。\n");
scanf("%d",&k);
if(k!=9&&k!=0)
{
printf("是不是显示结果：\n1.显示。2。不显示。\n");
scanf("%d",&m);
}
switch(k)
{
case 0:
Q=CreaList();
L=Q;
printf("是不是显示生成的数：\n1.显示。2。不显示。\n");
scanf("%d",&m);
if(m==1)
{
printf("\n30000个随机的数为:\n");
PrintfList(&L) ;
}
start1=clock();
L=BInsertSort(L,bj1,jh1);
if(m==1)
{
printf("\n30000个排好序的数为:\n");
PrintfList(&L);
}
finish1=clock();
printf("\n1.用折半插入排序法用的时间为%f秒；",((double)((finish1 - start1)/CLOCKS_PER_SEC)));
printf("\n 交换%ld次,比较%ld次。\n",jh1[0],bj1[0]);
L=Q;
start2=clock();
L=InsertSort(L,bj2,jh2);
finish2=clock();
printf("\n2.用直接插入排序法用的时间为%f秒；",((double)((finish2 - start2)/CLOCKS_PER_SEC)));
printf("\n 交换%ld次,比较%ld次。\n",jh2[0],bj2[0]);
L=Q;
start3=clock();
L=Bubble(L,bj3,jh3);
finish3=clock();
printf("\n3.用冒泡排序法用的时间为%f秒；",((double)((finish3 - start3)/CLOCKS_PER_SEC)));
printf("\n 交换%ld次,比较%ld次。\n",jh3[0],bj3[0]);
L=Q;
start4=clock();
L=HeapSort(L,bj4,jh4);
finish4=clock();
printf("\n4.用堆排序法用的时间为%f秒；",((double)((finish4 - start4)/CLOCKS_PER_SEC)));
printf("\n 交换%ld次,比较%ld次。\n",jh4[0],bj4[0]);
L=Q;
start5=clock();
L=SeledSort(L,bj5,jh5);
finish5=clock();
printf("\n5.用简单选择排序法用的时间为%f秒；",((double)((finish5-start5)/CLOCKS_PER_SEC)));
printf("\n 交换%ld次,比较%ld次。\n",jh5[0],bj5[0]);
L=Q;
start6=clock();
L=ShallSort(L,bj6,jh6);
finish6=clock();
printf("\n6.用希尔排序法用的时间为%f秒；",((double)((finish6-start6)/CLOCKS_PER_SEC)));
printf("\n 交换%ld次,比较%ld次。\n",jh6[0],bj6[0]);
L=Q;
start7=clock();
// MergeSort(&L,bj7,jh7);
finish7=clock();
// printf("\n7.用归并排序法用的时间为%f秒；",((double)((finish7-start7)/CLOCKS_PER_SEC)));
//printf("\n 交换%ld次,比较%ld次。\n",jh7[0],bj7[0]);
printf("\n7.暂时有错误!\n");
L=Q;
start8=clock();
L=QuickSort(L,bj8,jh8);
finish8=clock();
printf("\n8.用快速排序法用的时间为%f秒；",((double)((finish8-start8)/CLOCKS_PER_SEC)));
printf("\n 交换%ld次,比较%ld次。\n",jh8[0],bj8[0]);
goto start;
case 1:
L=CreaList();
start1=clock();
printf("%f\n",start1);
L=BInsertSort(L,bj1,jh1);
finish1=clock();
printf("%f\n",finish1);
if(m==1)
{
printf("\n30000个用折半插入排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用折半插入排序法用的时间为%f秒；",((double)((finish1 - start1)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh1[0],bj1[0]);
goto start;
case 2:
L=CreaList();
start2=clock();
L=InsertSort(L,bj2,jh2);
finish2=clock();
if(m==1)
{
printf("\n30000个用直接插入排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用直接插入排序法用的时间为%f秒；",((double)((finish2 - start2)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh2[0],bj2[0]);
goto start;
case 3:
L=CreaList();
start3=clock();
L=Bubble(L,bj3,jh3);
finish3=clock();
if(m==1)
{
printf("\n30000个用冒泡排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用冒泡排序法用的时间为%f秒；",((double)((finish3 - start3)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh3[0],bj3[0]);
goto start;
case 4:
L=CreaList();
start4=clock();
L=HeapSort(L,bj4,jh4);
finish4=clock();
if(m==1)
{
printf("\n30000个用堆排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用堆排序法用的时间为%f秒；",((double)((finish4 - start4)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh4[0],bj4[0]);
goto start;
case 5:
L=CreaList();
start5=clock();
L=SeledSort(L,bj6,jh6);
finish5=clock();
if(m==1)
{
printf("\n30000个用简单选择排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用简单选择排序法用的时间为%f秒；",((double)((finish5 - start5)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh5[0],bj5[0]);
goto start;
case 6:
L=CreaList();
start6=clock();
L=ShallSort(L,bj6,jh6);
finish6=clock();
if(m==1)
{
printf("\n30000个用希尔排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用希尔排序法用的时间为%f秒；",((double)((finish6 - start6)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh6[0],bj6[0]);
goto start;
case 7:
L=CreaList();
start7=clock();
MergeSort(&L,bj7,jh7);
finish7=clock();
if(m==1)
{
printf("\n30000个用归并排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用归并排序法用的时间为%f秒；",((double)((finish7-start7)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh7[0],bj7[0]);
goto start;
case 8:
L=CreaList();
start8=clock();
L=QuickSort(L,bj8,jh8);
finish8=clock();
if(m==1)
{
printf("\n30000个用快速排序法排好序的数为:\n");
PrintfList(&L);
}
printf("\n用快速排序法用的时间为%f秒；",((double)((finish8-start8)/CLOCKS_PER_SEC)));
printf("\n交换%ld次,比较%ld次。\n",jh8[0],bj8[0]);
goto start;
case 9:
{
end: printf("确定退出吗？\n1.确定。2.取消。\n");
scanf("%d",&t);
if(t==1)
{
printf(" \n 由于水平和时间的限制，不妥之处在所难免，恳请批评指正!!!——孔刚；侯光林。\n 谢谢光临!!!!\n");
printf(" 希望老师能在百忙之中把没实现的地方给调试一下。给出错误原因。谢谢！！\n") ;
printf(" \n 发E-mail到whhxkg@yahoo.com.cn。\n") ;
for(i=0;i<10000000000L;++i);
break;
}
else goto start1;
}
default : goto start1;
}
}
else if(n==2) goto end;
else goto start1;
return 1;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -