8645 归并排序（非递归算法）

SCAU数据结构OJ第六章

8645 归并排序（非递归算法）

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

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int M=1e5+5;
int a[M],n;

void Print()
{
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
void MergeSort(int num[],int l,int mid,int r)
{
    int *tmp=new int[r-l];//临时数组
    int i=l,j=mid,k=0;
    while(i<mid && j<r)
    {
        if(num[i]>num[j])
        {
            tmp[k++]=num[j++];
            continue;
        }
        tmp[k++]=num[i++];
    }//可能有左或者右子序列为空了，所以有下面的while
    while(i<mid)
    {
        tmp[k++]=num[i++];
    }
    while(j<r)
    {
        tmp[k++]=num[j++];
    }
    for(int i=0;i<k;i++)//最后把临时数组的数据搬回原数组
    {
        num[l++]=tmp[i];
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    int width = 1;
    while (width < n)
    {
        for(int start = 1; start <= n; start += width*2)
        {
            int mid = start + width;
            int end = start + 2*width;
            if(mid > n)
            {
                mid = n + 1;
            }
            if(end > n)
            {
                end = n + 1;
            }
            MergeSort(a, start, mid, end);
        }
        Print();
        width *= 2;
    }

    return 0;
}