[求助] 自然合并排序的算法
发布网友
发布时间：2022-04-22 05:11
共1个回答
热心网友
时间：2023-07-16 17:50
#include "stdio.h" //输入输出的库函数
#include "stdlib.h" //自然生成数据的库函数
int n; //全局变量，数组的长度
//函数的定义
void zgb(int *p); //自然分组的规划
void zgb1(int x,int y,int *q,int *p,int m); //递归实现的分治策略
void zgb2(int x,int y,int z,int *p); //排序函数
int main() //主函数
{
int i,m;
char ch=13; //变量的定义
while(1) //主菜单选择的循环
{
if(ch==13); //判断控制换行
system("cls"); //清屏
printf("------------请选择：--------------\n1、运行程序。\n0、退出程序。\n"); //主菜单
scanf("%d",&m); //接受菜单选择值
system("cls"); //清屏
if(!m) //判断程序是否执行。
exit(0); //如果m的值非1，则执行退出
printf("请输入数列的长度n。\n"); //提示语句
scanf("%d",&n); //从键盘输入一个值给n，规定数组的长度
int *a=new int[n]; //定义原数据数组
printf("随机数列如下：\n");
for(i=0; i<n; i++)
printf("%4d",a[i]=rand()%100); //动态生成数组的数据
printf("\n");
zgb(a); //调用自然分组的函数
printf("自然归并排序的结果如下：\n");
for(i=0; i<n; i++)
printf("%4d",a[i]); //输入最终排序号的结果数组
printf("\n");
scanf("%c%c",&ch,&ch); //接受最终的回车符，进入主菜单的下次循环
}
return 0;
}
void zgb(int *p) //自然分组函数
{
int i,m;
int *b=new int[n];//定义保存自然分组的起始下标值的数组
m=0;
b[0]=0;
for(i=1; i<n-1; i++)
if(p[i]>p[i+1]) //判断取得起始下标的值
b[m+=1]=i+1;
printf("每次排序前的分段下标如下：\n");
while(1) //进入分治策略的循环
{
for(i=0; i<=m; i++)
printf("%d\t",b[i]); //输出每次进入排序前的自然分组的起始下标值
printf("\n");
int k=0;
zgb1(0,m,b,p,m); //调用递归分治策略的函数
for(i=0; i<=m; i++)
{
if(b[i]!=-1&&b[k]==-1)
{
b[k]=b[i];
b[i]=-1; //合并后的起始下标的位子去除
}
if(b[k]!=-1)
k++;
}
m=k-1;
if(m<=0) //控制循环的退出
{
printf("0\n");
break;
}
}
}
void zgb1(int x,int y,int *q,int *p,int m) //分治策略函数
{
if(y-x==1) //判断下标的值域
{
if(y==m) //判断临界值，选择排序值的调用
zgb2(q[x],q[y],n,p);
else
zgb2(q[x],q[y],q[y+1],p); //调用排序函数
q[y]=-1;
}
int h=(x+y)/2; //计算规划值
if(y-x>=2)
{
zgb1(x,h,q,p,m); //递归调用函数本身
zgb1(h+1,y,q,p,m);
}
}
/*
排序函数
*/
void zgb2(int x,int y,int z,int *p)
{
int i,j,k,s;
for(i=y; i<z; i++)
for(j=x; j<z; j++)
if(p[i]<p[j])
{
k=p[i];
p[i]=p[j];
p[j]=k;
}
}
