实现真正意义上的合并排序

浏览数：16 / 时间：2015年06月08日

（算法老师布置这道题好长时间了，可是一直没有思路，真的是憋出来的代码啊）

真正意义上的合并排序是按照给的数组来判断的，它分的不是两两一组，在四四一组排序，直到完全排完序，真正意义上的合并排序是指先在数组上找到已有序的数组，分成几块，在进行合并。

代码如下：

#include <stdio.h>
#define N 10
#define flag1 1
#define flag2 2
int *FindOrder(int *a,int *b) //找到数组里有序的一段
{

int i=0,j=0;
while(i>=0&&i<N)
{

if(a[i]==a[i+1]-1)
{
b[j]=flag1;

}
else
{
b[j]=0;
}
i++;
j++;

}
for(i=0;i<N;i++)
{
if(b[i]==flag1&&b[i+1]==0)
{
b[i+1]=flag2;
}
}

return b;
}
void Sort(int *a,int n,int *b)//排序
{
int i,j;
int t;
for(i=0;i<n-1;i++)
{ for(j=i+1;j<n;j++)
{

if(a[i]<a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
for(i=0;i<n;i++)
{
b[i]=flag1;
}
b[n-1]=flag2;
for(i=0;i<n;i++) //为了让排好序的数组融入原来的找到的有序数组所做的措施
{
if(b[i]==flag2&&b[i+1]==flag1)
{
b[i]=flag1;
}
}
}
int Find2(int *b) //找到数组中第一个2的位置
{
int i,j=0;
for(i=0;i<N;i++)
{
if(b[i]==2)
{
break;

}
}

return i;

}
int * DevideGroup(int *b,int *a) //分块
{
int i,j;
int p=0;
int m[N]={0};
while(p<5)
{
for(i=0;i<N;i++)
{
if(b[i]==0&&b[i+1]==0)
{
Sort(a+i,2,b+i);
break;

}
}

for(j=0;j<N;j++)
{
if(b[j]==0&&b[j+1]==flag1)
{
Sort(a+j,Find2(b)+1,b+j);
break;
}
}
for(j=0;j<N;j++)
{
if(b[j]==flag1&&b[j+1]==flag1)
{
Sort(a+j,Find2(b)+1,b+j);
break;
}
}
for(j=0;j<N;j++)
{
if(b[j]==flag2&&b[j+1]==0)
{
b[j]=flag1;
b[j+1]=flag2;
break;
}
}
for(j=0;j<N;j++)
{
if(b[j]==flag1&&b[j+1]==flag1)
{
Sort(a+j,Find2(b)+1,b+j);
break;
}
}
p++;
}
return a;

}
int main(void)
{
int a[N]={3,1,2,4,5,6,7,0,9,11};//已知数组
int b[N]={0};//辅助数组，这个数组记录的是有序的数组位置，0 表示自己一个，凡是以1开头2结尾的是有序的数组元素、
int *f,i,*m;
printf("你的数据为:\n");
for(i=0;i<N;i++)
{
printf("%d,",a[i]);
}
f=FindOrder(a,b);
m=DevideGroup(f,a);
printf("\n排序后为：\n");
for(i=0;i<N;i++)
{
printf("%d,",m[i]);
}
printf("\n");
}
//3,1,2,4,5,6,7,0,9,11
//4,3,1,2,3,6,7,3,3,3
//5,4,5,2,5,6,8,4,7,9