#include "stdlib.h"
#define MAXSIZE 150
#include <stdio.h>
typedef struct
{
int key;
}RECNODE;
int b,t;
int MakeList(RECNODE *r)
{
int j,k;
printf("\n请输入初始数据(每个数据以空格隔开，-1结束）： ");
k=0;
scanf("%d",&j);
while(j!=-1)
{
k++;
r[k].key=j;
scanf("%d",&j);
}
return k;
}
void UndealoutList(RECNODE *r,int n)
{
int i;
printf("\n未排序前的数据 ： ");
for(i=0;i<n;i++)
printf(" %d",r[i+1].key);
printf("\n\n");
}
void DealoutList(RECNODE*r,int n)
{
int i;
printf("排序后的数据 ： ");
for(i=0;i<n;i++)
printf(" %d",r[i+1].key);
printf("\n\n");
printf("交换或比较的次数： %d\n",b);
printf("排序的趟数： %d\n",t);
}
void InsertSort(RECNODE*r,int n)//直接插入排序//
{
int i,j;
b=0,t=0;
for(i=2;i<=n;i++)
{
r[0]=r[i];
j=i-1;
while(r[0].key<r[j].key)
{
r[j+1]=r[j];
j--;
b++;
}
r[j+1]=r[0];
b++;
t++;
}
}
void BubleSort(RECNODE *r,int n) //冒泡排序//
{
int i,j;
b=0,t=0;
RECNODE temp;
for(i=1;i<n;i++)
{
for(j=n-1;j>=i;j--)
if(r[j+1].key<r[j].key)
{
temp=r[j+1];
r[j+1]=r[j];
r[j]=temp;
b++;
}
else b++;
t++;
}
}
int Partition(RECNODE*r,int*low,int*high)//一躺快速排序//
{
int i,j;
static int w=0;
RECNODE temp;
i=*low;
j=*high;
temp=r[i];
do
{
while((r[j].key>=temp.key)&&(i<j))
{
j--;
w++;
}
if(i<j)
{
r[i]=r[j];
i++;
w++;
}
while((r[i].key<=temp.key)&&(i<j))
{
i++;
w++;
}
if(i<j)
{
r[j]=r[i];
j--;
w++;
}
}while(i!=j);
r[i]=temp;
b=w;
return i;
}
void QuickSort(RECNODE*r,int start,int end)//快速排序//
{
int i;
static int q=0;
if(start<end)
{
i= Partition(r,&start,&end);
q++;
QuickSort(r,start,i-1);
QuickSort(r,i+1,end);
}
t=q;
}
void SeleSort(RECNODE*r,int n)//直接选择排序//
{
int i,j,z;
b=0,t=0;
RECNODE temp;
for(i=1;i<n;i++)
{
z=i;
for(j=i+1;j<=n;j++)
if(r[j].key<r[z].key)
{
z=j;
b++;
}
else b++;
if(z!=i)
{
temp=r[i];
r[i]=r[z];
r[z]=temp;
}
t++;
}
}
void ShellSort(RECNODE *r,int n)//希尔排序//
{
int i,j,dk;
n=n+1;
b=0,t=0;
dk=n/2;
while(dk>0)
{
for(i=dk+1;i<n;++i)
if(r[i].key<r[i-dk].key)
{
r[0]=r[i];
for(j=i-dk;j>0&&r[0].key<r[j].key;j-=dk)
{
r[j+dk]=r[j];
b++;
}
r[j+dk]=r[0];
}
dk=dk/2;
t++;
}
}
void Sift(RECNODE*r,int i,int m)
{
int j;
static int x=0;
RECNODE temp;
temp=r[i];
j=2*i;
while(j<=m)
{
if(j<m&&(r[j].key<r[j+1].key))
{
j++;
x++;
}
if(temp.key<r[j].key)
{
r[i]=r[j];
i=j;
j=2*i;
x++;
}
else x++; break;
}
r[i]=temp;
b=x;
}
void HeapSort(RECNODE*r,int n) //堆排序//
{
RECNODE temp;
int i;
t=0;
for(i=n/2;i>=1;i--)
Sift(r,i,n);
for(i=n;i>=2;i--)
{
temp=r[1];
r[1]=r[i];
r[i]=temp;
Sift(r,1,i-1);
t++;
}
}
int main()
{
RECNODE a[MAXSIZE];
int len,p;
do
{
printf("**********************\n"); //显示界面
printf("* 菜 单 *\n");
printf("**********************\n");
printf("* 1---直接排序 *\n");
printf("* 2---冒泡排序 *\n");
printf("* 3---快速排序 *\n");
printf("* 4---选择排序 *\n");
printf("* 5---堆排序 *\n");
printf("* 6---希尔排序 *\n");
printf("* 0---退出 *\n");
printf("**********************\n");
printf("\n请在上述序号中选择一个并输入： ");
scanf("%d",&p);
switch(p)
{
case 1:len=MakeList(a);
UndealoutList(a,len);
InsertSort(a,len);
DealoutList(a,len);
break;
case 2:len=MakeList(a);
UndealoutList(a,len);
BubleSort(a,len);
DealoutList(a,len);
break;
case 3:len=MakeList(a);
UndealoutList(a,len);
QuickSort(a,1,len);
DealoutList(a,len);
break;
case 4:len=MakeList(a);
UndealoutList(a,len);
SeleSort(a,len);
DealoutList(a,len);
break;
case 5:len=MakeList(a);
UndealoutList(a,len);
HeapSort(a,len);
DealoutList(a,len);
break;
case 6:len=MakeList(a);
UndealoutList(a,len);
ShellSort(a,len);
DealoutList(a,len);
break;
case 0:break;
default:printf("输入错误！请重新输入!\n");break;
}
}while(p!=0);
}
