#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 100
typedef struct
{
int key;
char otherinfo;
}Elem;
typedef struct
{
Elem r[N+1];//r[0]闲置或用作“哨兵”
int length;
}Sqlist;
void InitSqlist(Sqlist *L)
{
L->length =N;
}
void print(Sqlist *L)//排序后输出
{
int i;
for(i=1;i<=L->length ;i++)
printf("%5d",L->r[i]);
printf("/n");
}
//起泡排序
void gensort(Sqlist *L)
{
int i,j;
int s=0,t=0;//t--比较次数 s--移动次数
int temp;
int change;
for(i=1,change=1;i<=L->length&&change==1 ;i++)
{
change=0;
for(j=i+1;j<=L->length ;j++)
{
t++;
if(L->r [i].key >L->r [j].key )
{
temp=L->r [i].key ;
L->r [i].key =L->r [j].key ;
L->r [j].key =temp;
s+=3;
change=1;
}
}
}
printf("起泡排序后：/n");
print(L);
printf("起泡排序 比较次数：%d 移动次数：%d/n",t,s);
}
//直接插入排序
void InsertSort(Sqlist *L)
{
int i,j;
int s=0,t=0;
for(i=2;i<=L->length ;i++)
{ t++;
if(L->r [i].key <L->r [i-1].key )
{
L->r [0].key =L->r [i].key ;
s++;
j=i-1;
t++;
while(L->r [0].key <L->r [j].key )
{
L->r [j+1].key =L->r [j].key ;//后移
j--;
s++;
t++;
}
L->r [j+1].key =L->r [0].key ;//插入到正确位置
s++;
}
}
printf("直接插入排序后：/n");
print(L);
printf("直接插入排序 比较次数: %d 移动次数: %d/n",t,s);
}
//简单选择排序
void simpleSort(Sqlist *L)
{
int i,j,k;
int s=0,t=0;
int temp;
for(i=1;i<=L->length ;i++)
{
k=i; //指示最小元素的下标
for(j=i+1;j<=L->length ;j++)
{
t++;
if(L->r [k].key >L->r [j].key )
k=j;
}
if(k!=i)
{
temp=L->r [k].key ;
L->r[k].key =L->r [i].key ;
L->r [i].key =temp;
s+=3;
}
}
printf("简单选择排序后：/n");
print(L);
printf("简单选择排序 比较次数：%d 移动次数: %d/n",t,s);
}
// 快速排序
int Partion(Sqlist *L,int low,int high,int *t,int *s)
{
int pivot;
L->r [0].key =L->r [low].key ;
(*s)++;
pivot=L->r [low].key ;
while(low<high)
{
(*t)++;
while(low<high&&L->r [high].key >=pivot)
{
--high;
(*t)++;
}
L->r [low].key =L->r [high].key ;
(*s)++;
(*t)++;
while(low<high&&L->r [low].key <=pivot)
{
++low;
(*t)++;
}
L->r [high].key =L->r [low].key ;
(*s)++;
}
L->r [low].key =L->r [0].key ;
(*s)++;
return low;
}
void Qsort(Sqlist *L,int low,int high,int *t,int *s)
{
int pivot;
if(low<high)
{
pivot=Partion(L,low,high,t,s);
Qsort(L, low,pivot-1 ,t,s);
Qsort(L, pivot+1,high,t,s );
}
}
void QuickSort(Sqlist *L)
{
int s=0,t=0;
Qsort(L,1,L->length ,&t,&s);
printf("快速排序后：/n");
print(L);
printf("快速排序 比较次数：%d 移动次数：%d/n",t,s);
}
//希尔排序
void ShellInsert(Sqlist *L,int dk, int *s,int *t)
{
int i,j;
for(i=dk+1;i<=L->length ;i++)
{
(*t)++;
if(L->r [i].key <L->r [i-dk].key )
{
L->r [0].key =L->r [i].key ;
(*s)++;
j=i-dk;
(*t)++;
while(j>0&&L->r [0].key <L->r [j].key )
{
L->r [j+dk].key =L->r [j].key ;
(*t)++;
(*s)++;
j-=dk;
}
L->r [j+dk].key =L->r [0].key ;
(*s)++;
}//if
}//for
}
void ShellSort(Sqlist *L)
{
int i,j,dk;
int s=0,t=0;
for(i=(int)log(L->length +1);i>0;i--) //形成增量
for(j=i;j<=(int)log(L->length +1);j++)
{
dk =(int)pow(2,j-i+1)-1;
ShellInsert(L,dk, &s,&t);
}
printf("希尔排序后：/n");
print(L);
printf("希尔排序 比较次数:%d,移动次数:%d/n",t,s);
}
//堆排序
void HeapAdjust(Sqlist *L,int x,int y,int *t,int *s)
{
int rc,i;
rc=L->r [x].key ;
for(i=2*x;i<=y;i*=2)
{
(*t)++;
if(i<y&&L->r [i].key <L->r [i+1].key )//沿key较大的孩子结点向下筛选
++i;
(*t)++;
if(rc>=L->r[i].key )
break;
L->r [x].key =L->r [i].key ;
(*s)++;
x=i;
}
L->r [x].key =rc;
(*s)++;
}
void HeapSort(Sqlist *L)
{
int i,s=0,t=0;
int temp;
for(i=L->length /2;i>0;--i)
HeapAdjust(L,i,L->length , &t,&s);
for(i=L->length ;i>1;--i)
{
temp=L->r [1].key ;
L->r [1].key =L->r [i].key ;
L->r [i].key =temp;
s+=3;
HeapAdjust(L,1,i-1,&t,&s);
}
printf("堆排序后：/n");
print(L);
printf("堆排序 比较次数：%d 移动次数：%d/n",t,s);
}
void Sort(Sqlist *L1,Sqlist *L2,Sqlist *L3,Sqlist *L4,Sqlist *L5,Sqlist *L6)
{
gensort(L1);
InsertSort(L2);
simpleSort(L3);
ShellSort(L4);
QuickSort(L5);
HeapSort(L6);
}
void suiji(Sqlist *L1,Sqlist *L2,Sqlist *L3,Sqlist *L4,Sqlist *L5,Sqlist *L6)
{
int i;
for(i=1; i<=L1->length ; i++)
{
L1->r[i].key =rand()%100;
L2->r [i].key =L1->r [i].key ;
L3->r[i].key =L1->r [i].key ;
L4->r [i].key =L1->r [i].key ;
L5->r [i].key =L1->r [i].key ;
L6->r [i].key =L1->r [i].key ;
printf("%5d", L1->r [i].key );
}
}
void main()
{
int i,j;
Sqlist L1,L2,L3,L4,L5,L6;
InitSqlist(&L1);
InitSqlist(&L2);
InitSqlist(&L3);
InitSqlist(&L4);
InitSqlist(&L5);
InitSqlist(&L6);
////正序数据
for(i=1,j=1;i<=L1.length ,j<=L1.length ;i++,j++)
{ L1.r[i].key =j;
L2.r[i].key =j;
L3.r[i].key =j;
L4.r[i].key =j;
L5.r[i].key =j;
L6.r[i].key =j;
}
printf("排序前正序数组:/n");
for(i=1;i<=L1.length ;i++)
printf("%5d",L1.r[i]);
printf("/n");
Sort(&L1,&L2,&L3,&L4,&L5,&L6);
////逆序数据
for(i=L1.length ,j=1;i>0,j<=L1.length ;i--,j++)
{ L1.r [j].key =i;
L2.r [j].key =i;
L3.r [j].key =i;
L4.r [j].key =i;
L5.r [j].key =i;
L6.r [j].key =i;
}
printf("排序前逆序数组:/n");
for(i=1;i<=L1.length ;i++)
printf("%5d",L1.r [i].key );
printf("/n");
Sort(&L1,&L2,&L3,&L4,&L5,&L6);
////乱序数据
printf("第一组乱序：/n");
suiji(&L1,&L2,&L3,&L4,&L5,&L6);
printf("/n");
Sort(&L1,&L2,&L3,&L4,&L5,&L6);
printf("第二组乱序：/n");
suiji(&L1,&L2,&L3,&L4,&L5,&L6);
printf("/n");
Sort(&L1,&L2,&L3,&L4,&L5,&L6);
printf("第三组乱序：/n");
suiji(&L1,&L2,&L3,&L4,&L5,&L6);
printf("/n");
Sort(&L1,&L2,&L3,&L4,&L5,&L6);
}