#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
typedef int keyType;
typedef struct
{
keyType key;/*关键字域*/
/*其它域*/
}RecordType; /*记录类型*/
void DisPlay(RecordType R[],int n);
void InsertSort(RecordType r[],int n)
/*对表r中的第1到第n个记录进行直接插入排序,r[0]为监视哨*/
{
int i,j;
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--; /*记录后移*/
}
r[j+1]=r[0]; /*把存放在r[0]中的原记录插入正确位置*/
}
}
void ShellSort(RecordType r[],int n)
/*对表r中的第1到第n个记录进行希尔排序,r[0]为监视哨*/
{
int i,j,d;
for(d=n/2;d>0;d=d/2) /*初始增量为n/2,每次缩小增量值为d/2*/
{
for(i=d+1;i<=n;i++)
{
r[0]=r[i];
j=i-d; /* 前后记录位置的增量是dk,而不是1*/
/*将L.r[i]插入有序增量子表*/
while(j>=0&&r[0].key<r[j].key) /*将r[i]插入有序子表*/
{
r[j+d]=r[j];
j=j-d;
}/*记录后移,查找插入位置 */
r[j+d]=r[0]; /*插入*/
}
}
}
void Bubble_sort(RecordType r[],int n)
/*对表r中的第1到第n个记录进行希尔排序,r[0]为临时交换空间*/
{
int i,j;
int isExcheng; /*交换标志*/
for(i=1;i<n;i++)
{
isExcheng=0; /* isExcheng=0为未交换*/
for(j=1;j<=n-i;j++)
{
if(r[j].key>r[j+1].key)
{ /*如前者大于后,交换*/
r[0]=r[j+1];
r[j+1]=r[j];
r[j]=r[0];
isExcheng=1; /*isExcheng=1为发生交换*/
}
}
if(isExcheng==0)break; /*未交换,排序结束*/
}
}
int Partition(RecordType r[],int low,int high)
/*对表r中的第low到第high个记录进行一次快速排序的划分,把关键字小于r[low].key的记录放在r[low]前面,大于r[low].key的记录放在r[low]后面*/
{
r[0]= r[low]; /* 把r[low]放在r[0]*/
while (low<high) /*用r[low]进行一趟划分*/
{
/*在high端,寻找一个比r[low].key小的记录放入low*/
while (low<high &&r[high].key>=r[0].key)
--high;
r[low]=r[high];
/*在low端,寻找一个比r[low].key大的记录放入high*/
while (low<high &&r[low].key<=r[0].key)
++low;
r[high]=r[low];
}
r[low]=r[0];
return low; //返回划分后的基准记录的位置
}
void Quicksort(RecordType r[],int low,int high)
/*对表r中的第low到第high个记录进行快速排序*/
{
int loc;
if (low<high)
{
/*对第low到第high个记录进行一次快速排序的划分*/
loc=Partition(r,low,high);
Quicksort(r,low,loc-1); /*对前半区域进行一次划分*/
Quicksort(r,loc+1,high); /*对后半区域进行一次划分*/
}
}
void Selectsort(RecordType r[],int n)
/*对表r中的第1到第n个记录进行简单选择排序,r[0]为临时交换空间*/
{
int i,j,min;
for(i=1;i<n;i++)
{
min=i;
/*在i...n 范围内寻找一个最小元素放入r[i]中*/
for (j=i+1;j<=n;++j)
if (r[min].key>r[j].key)
min=j;
if(min!=i)
{
r[0]=r[min];
r[min]=r[i];
r[i]=r[0];
}
}
}
void Creatheap(RecordType r[],int m,int n)
/*对表r中的结点编号为m到n的元素进行建堆,r[0]为临时交换空间*/
{
int i,j,flag;
i=m;
j=2*i; /*j为i的左孩子*/
r[0]=r[i];
flag=0;
while(j<=n&&flag!=1) /*沿值较小的分支向下筛选*/
{
if (j<n&&r[j].key>r[j+1].key)
j++;/*选取孩子中值较小的分支*/
if(r[0].key<r[j].key)
flag=1;
else
{
r[i]=r[j];
i=j;
j=2*i; /*继续向下筛选*/
r[i]=r[0];
}
}
}
void Heapsort(RecordType x[],int n)
/*/*对表r中的第1到第n个记录进行堆排序,r[0]为临时交换空间*/
{
int i;
for (i=n/2;i>=1;i--)
Creatheap(x,i,n); /*初始化堆*/
printf("Output x[]:");
/*输出堆顶元素,并将最后一个元素放到堆顶位置,重新建堆*/
for (i=n;i>=1;i--)
{
printf("%4d",x[1]); /*输出堆顶元素*/
x[1]=x[i]; /*将堆尾元素移至堆顶*/
Creatheap(x,1,i); /*整理堆*/
}
printf("\n");
}
void Merge (RecordType a[],RecordType b[],int i,int m, int n)
//将有序表a[i..m]以及a[m+1..n]有序归并到b[i..m]中
{ int la,lb,lc;
la=i;
lb=m+1;
lc=i; //序列 la,lb,lc 的始点
while(la<=m &&lb<=n)
if (a[la].key<a[lb].key)
b[lc++].key=a[la++].key ; //有序合并
else
b[lc++].key=a[lb++].key;
while(la<=m)
b[lc++].key=a[la++].key;
while(lb<=n)
b[lc++].key=a[lb++].key;
}
void Mergesort (RecordType a[],RecordType b[],int s,int t)
//将有序表 a[s..t]有序归并排序到 b[s..t]中
{
int m;
RecordType c[MAXSIZE+1];
if (s==t) b[s].key=a[s].key;
else
{
m=(s+t)/2;
Mergesort( a,c,s,m);
//show(b,N);getchar();
Mergesort( a,c,m+1,t);
//show(b,N);getchar();
Merge(c,b,s,m,t);
}
}
void DisPlay(RecordType R[],int n)
{
int i;
for(i=1;i<=n;i++)
printf("%3d",R[i]);
}
void main()
{
int ch;
char exit='N';
RecordType R[MAXSIZE+1]={0,34, 44, 43, 12, 53, 55,73, 64, 77,13};
do
{
system("CLS");
printf("\t\t******排序前的序列**************************\n");
printf("\t\t* ");DisPlay(R,MAXSIZE);
printf(" *\n\n");
printf("\t\t******请选择排序算法************************\n");
printf("\t\t* 1.直接插入排序.....................(1) *\n");
printf("\t\t* 2.希尔排序.........................(2) *\n");
printf("\t\t* 3.冒泡排序.........................(3) *\n");
printf("\t\t* 4.快速排序.........................(4) *\n");
printf("\t\t* 5.简单选择排序.....................(5) *\n");
printf("\t\t* 6.堆排序...........................(6) *\n");
printf("\t\t* 7.二路归并排序.....................(7) *\n");
printf("\t\t* 8.退出.............................(8) *\n");
printf("\t\t********************************************\n");
printf("\n请选择操作代码:");
scanf("%d",&ch);
switch(ch)
{
case 1:
InsertSort(R,MAXSIZE);
printf("排序后的序列:");
DisPlay(R,MAXSIZE);
printf("\n");
system("pause");
break;
case 2:
ShellSort(R,MAXSIZE);
printf("排序后的序列:");
DisPlay(R,MAXSIZE);
printf("\n");
system("pause");
break;
case 3:
Bubble_sort(R,MAXSIZE);
printf("排序后的序列:");
DisPlay(R,MAXSIZE);
printf("\n");
system("pause");
break;
case 4:
Quicksort(R,1,MAXSIZE);
printf("排序后的序列:");
DisPlay(R,MAXSIZE);
printf("\n");
system("pause");
break;
case 5:
Selectsort(R,MAXSIZE);
printf("排序后的序列:");
DisPlay(R,MAXSIZE);
printf("\n");
system("pause");
break;
case 6:
Heapsort(R,MAXSIZE);
system("pause");
break;
case 7:
Mergesort(R,R,1,MAXSIZE);
printf("排序后的序列:");
DisPlay(R,MAXSIZE);
printf("\n");
system("pause");
break;
case 8:
getchar();
printf("\n您是否真的要退出程序(Y/N):");
exit=getchar();getchar();
break;
default:
printf("\n无效输入,请重新选择...:");
}
}while(exit!='y'&&exit!='Y');
}
评论0
最新资源