Description
用函数实现归并排序（非递归算法），并输出每趟排序的结果
输入格式
第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据
输出格式
每行输出每趟排序的结果，数据之间用一个空格分隔
输入样例
10 5 4 8 0 9 3 2 6 7 1
输出样例
4 5 0 8 3 9 2 6 1 7 0 4 5 8 2 3 6 9 1 7 0 2 3 4 5 6 8 9 1 7 0 1 2 3 4 5 6 7 8 9
感觉非递归的归并排序有点难理解，我先理解了一下递归的归并排序，然后再理解非递归的就容易多了。递归方法的我也放在了后面。（最好是可以自己动手推一下，如果懒得动手可以看一下B站这个up主：纯情少狼雷格西 视频名字叫：二路归并排序算法 递归手动执行过程）
做这个题，关键点就是写出merge排序函数，然后就是处理好每个划分与传入merge函数的下标的关系，理解记忆下来。
#include<stdio.h>
int a[1000],n;
void print() {
for(int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
//负责排序,就是把原数组中low-mid和（mid+1）-high这部分的数据排序
void merge(int low,int mid,int high) //把每个要排序的分块视作左右两个数组之间的排序
{
int nl,nr;
nl=mid-low+1; //左边数组的长度
nr=high-mid; //右边数组的长度
int L[nl],R[nr]; //左右两个数组
for(int i=0;i<nl;i++) //用左右两个数组把原数组中对应要排序的位置的数据存储进来
{
L[i]=a[low+i];
}
for(int j=0;j<nr;j++)
{
R[j]=a[mid+1+j];
}
int i=0,j=0,k=0;
//像合并顺序表那样把左右两个数组排好序
while(i<nl&&j<nr)
{
if(L[i]<=R[j])
{
a[low+k]=L[i];
k++;
i++;
}
else
{
a[low+k]=R[j];
k++;
j++;
}
}
while(i<nl)
{
a[low+k]=L[i];
k++;
i++;
}
while(j<nr)
{
a[low+k]=R[j];
k++;
j++;
}
}
//负责分块
void split(int span)
{
int nowlength=0; //目前有多大长度 被划出来 根据分块大小来排序
int low,mid,high;
while(nowlength+span*2-1<n) //分块大小为span，high下标多span*2-1个，high下标不能超n
{
low=nowlength;
high=nowlength+2*span-1;
mid=(low+high)/2;
merge(low,mid,high);
nowlength+=2*span; //更新划出来的长度，同时也是下次排序的low
}
//存在没有完全划分的情况
if(nowlength<n) //要重新确定排序时需要的mid和high值
{
merge(nowlength,nowlength+span-1,n-1); //high值就是最后一个
} //关于mid,因为是按1,2,4..这样划分来排的，所以nowlength+span-1就可以,可以自己推一下
}
//负责确定每个分块的大小：1,2,4,8...
void mergesort()
{
int span=1;
while(span<n)
{
split(span);
print();
span*=2;
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i <n; i++) {
scanf("%d", &a[i]);
}
mergesort();
return 0;
}
下面是递归法的：
#include<stdio.h>
int a[1000],n;
void print() {
for(int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
void merge(int low,int mid,int high)
{
int nl,nr;
nl=mid-low+1;
nr=high-mid;
int L[nl],R[nr];
for(int i=0;i<nl;i++)
{
L[i]=a[low+i];
}
for(int j=0;j<nr;j++)
{
R[j]=a[mid+1+j];
}
int i=0,j=0,k=0;
//int flag=0;
while(i<nl&&j<nr)
{
if(L[i]<=R[j])
{
a[low+k]=L[i];
k++;
i++;
}
else
{
a[low+k]=R[j];
k++;
j++;
//flag=1;
}
}
while(i<nl)
{
a[low+k]=L[i];
k++;
i++;
}
while(j<nr)
{
a[low+k]=R[j];
k++;
j++;
}
//if(flag==1) print();
}
//递归法
void mergesort(int low,int high)
{
if(low<high)
{
int mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i <n; i++) {
scanf("%d", &a[i]);
}
mergesort(0,n-1);
print();
return 0;
}