归并排序c++

归并排序算法是在分治算法基础上设计出来的一种排序算法，它可以对指定序列完成升序（由小到大）或降序（由大到小）排序，对应的时间复杂度为O(nlogn)。

归并排序算法实现排序的思路是：

1. 将整个待排序序列划分成多个不可再分的子序列，每个子序列中仅有 1 个元素；
2. 所有的子序列进行两两合并，合并过程中完成排序操作，最终合并得到的新序列就是有序序列。

确定分界点 ：mid =(l+r)/2

递归排序 left right

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9范围内），表示整个数列。

输出共一行，包含 n 个整数，表示排好序的数列。

1≤n≤100000

5
3 1 2 4 5

1 2 3 4 5

代码如下：

#include
using namespace std;
const int N = 100010;
int q[N], tem[N];
int n;

void merge_sort(int q[],int l,int r)
{
    if(l>=r)
        return;
    //确定分界点
    int mid = l + r >> 1;
    //递归排序
    merge_sort(q, l, mid);
    merge_sort(q, mid+1,r);
    //归并排序
    int i = l, j = mid + 1, k = 0;
    //判断大小
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])
            tem[k++] = q[i++];
        else
            tem[k++] = q[j++];
    }
    //将剩余的数直接排到后面
        while(i<=mid)
        {
            tem[k++] = q[i++];
        }
        while(j<=r)
        {
            tem[k++] = q[j++];
        }
        //将tmp[]数组存储的排序赋值给q[]
        for (int i = l, j = 0; i <= r;i++,j++)
        {
            q[i] = tem[j];
        }
    
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n;i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}