排序

【题目描述】

给定n和n(1 <= n <= 100000)个整数，要求从小到大给他们排序。

【输入描述】

第一行输入一个正整数n；

第二行输入n个整数。

【输出描述】

从小到大输出n个整数。

【样例输入】

3

3 1 2

【样例输出】

1 2 3

源代码：

#include<cstdio>
int n,num(0),i[100001],h[100001];
void x1(int t1,int t2)
{
    if (t1==t2) //分割到单个元素回溯。
      return;
    x1(t1,(t1+t2)/2);
    x1((t1+t2)/2+1,t2);
    int t=(t1+t2)/2,x=t1,y=t+1,num=t1;
    while (x<=t&&y<=t2) //小为先，指针进。
      if (i[x]<=i[y])
        h[num++]=i[x++];
      else
        h[num++]=i[y++];
    while (x<=t) //大为后，直接补。
      h[num++]=i[x++];
    while (y<=t2)
      h[num++]=i[y++];
    for (int a=t1;a<=t2;a++) //处理完后进行替换，保证子序列皆为有序。
      i[a]=h[a];
}
int main()
{
    scanf("%d",&n);
    for (int a=1;a<=n;a++)
      scanf("%d",&i[a]);
    x1(1,n); //归并排序。
    for (int a=1;a<=n;a++)
      printf("%d ",h[a]);
    return 0;
}